CS and Sugar
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65768/32768 K (Java/Others)
Total Submission(s): 190 Accepted Submission(s): 89
Problem Description
CS and Sugar find a new continent at the same time. Rare plants are all over this miraculous land, so they decided to take them home and sell it. But obviously, not all plants can be sold at a good price. Some plants are just usual weed. After some time of observation, they became self-taught botanists. CS and Sugar divided a rectangle area into n*m grids, and marked them with different values (maybe negative). They dig in turns to be fare, when all the plants in a grid are taken by the last person, and next person start to move on. The next person always chooses the one of the grids which are above and left to the last person, including the straight above or straight left. And even that, CS and Sugar still tried to compete with each other, and they always choose the available part with higher absolute value than last one no matter positive or negative. The first person can choose any grid to begin. Until someone is not able to make any move, they left. They are now debating who should dig first because they have already calculated how many advantages the first person can get.
Input
Multiple test cases (no more than 100), for each case:
The first line contains two integers n and m (0<n, m<=100), representing the rectangle area was divided into n*m parts.
Following n lines, each line contains m integers whose absolute value is no more than 100, representing the value in each part.
Output
For each case, output one integer, representing the maximum advantage the first person can get in total value.
Sample Input
1 5
-5 -4 -3 -2 -1
2 2
-7 -6
-6 5
3 2
-6 -5
-4 -4
2 4
Sample Output
Author
zyue1105
Source
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3883题意：两个那啥挖矿，轮流的。第一铲子落点任意自选。每一铲子的落点都要在上一铲子的“非严格”左上区间内，且格中value的绝对值要大于上一选格中value的绝对值。
两人都最优策略求自己最后总值最大。问最后的两人差值为多少。
解：
感谢ykprocess大神场上ac这题，赛后还给本菜讲题。YMYMYM！
乍一看像博弈。也差不多确实是，不过在两人均最优策略的情况下，这题转化为一个DP了。
从末态向初态推，消后效性；每一步都选择上一步（其实是后一步）最大的那个dp值，减掉它，就是当前状态的最优解。
状态转移就是dp[x][y] = (max(1..x,1..y)dp[i][j] == -inf)?map[x][y]:map[x][y] - max;
本题的两个特点，将读入的点全部排序，按照abs(val)降序>x降序>y降序排列。第一序保证了无后效性的关键，即先更新掉绝对值大的点，每次更新的时候就不用去判断当前点与查询出来的点绝对值大小关系了。后两个序其实没必要，只是保证了
绝对值相同的点同时更新而已：这样就可以使得xy坐标大的点先更新，从而不会让绝对值相同的点互相更新，这样会导致错误的结果。感谢james0zan大神给本菜讲解了这个序的关键作用。YMYMYMYM！
由于这题矩阵是100*100的。。所以如果每步naive的查询最大值，会让复杂度退化到O(100*4)的复杂度。所以果断上数据结构－－树状数组。二维树状数组使得查询最大值的复杂度降为(logn)^2。。所以该题的总复杂度为O(NM*log(N*M) + NM*log(N*M))=O(N^2*log^2(N))的。
二维树状数组查询最大值是第一次写，中间遇到不少困难。说几个要点：lowbit啥用不解释，更新结点最大值的时候是从小往大更新，因为当前结点会被x + lowbit(x) (<=n)的这些点们所管辖(if val > treearray[x][y] then update)。。而查询的时候则是从大往小查询，因为x - lowbit(x)管辖这些子矩阵中的最大值。
另外因为是二维的。。所以千万不要这么写：
for(;x > 0; x -= lowbit(x))
for(;y > 0; y -= lowbit(y))
这个太二了。。不解释。。一维这么写没关系。。二维就真的2b了。。。果断开个新变量啊少年，省代码会死啊。。。
还有初始化要用-inf。因为会有负数出现。
代码附在这里：
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 102
const int inf = ~0u >> 1;
int n,m,tr[maxn][maxn],dp[maxn][maxn],map[maxn][maxn];
int bit(int x){return x & -x;}
struct node
{
int x,y,val;
node(){}
node(int _x,int _y,int _val):x(_x),y(_y),val(_val){}
}no[maxn * maxn];
int ab(int x)
{return (x > 0)?x:-x;}
bool operator < (const node &a,const node &b)
{
return a.val > b.val || (a.val == b.val && a.x > b.x) || (a.val == b.val && a.x == b.x && a.y > b.y);
}
void init()
{
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
tr[i][j] = -inf;
}
void mod(int x,int y,int val)
{
for(int i = x;i <= n;i += bit(i))
for(int j = y;j <= m;j += bit(j))
if(tr[i][j] < val)
tr[i][j] = val;
}
int find(int x,int y)
{
int ans = -inf;
for(int i = x;i > 0; i -= bit(i))
for(int j = y;j > 0;j -= bit(j))
if(ans < tr[i][j])
ans = tr[i][j];
return ans;
}
int main()
{
while(scanf("%d %d",&n,&m) == 2)
{
int cnt = 0;
init();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
scanf("%d",&map[i][j]);
no[cnt++] = node(i,j,ab(map[i][j]));
}
sort(no,no + cnt);
for(int i = 0;i < cnt;i++)
{
int x = no[i].x,y = no[i].y;
int temp = find(x,y);
if(temp == -inf)
dp[x][y] = map[x][y];
else
dp[x][y] = map[x][y] - temp;
mod(x,y,dp[x][y]);
}
int ans = -inf;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(ans < dp[i][j])
ans = dp[i][j];
printf("%d\n",ans);
}
}
Backspace
backward paragraph