2015
04-13

# CS and Sugar

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.

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.

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.

1 5
-5 -4 -3 -2 -1
2 2
-7 -6
-6 5
3 2
-6 -5
-4  -4
2  4

1
4
3

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 128
int f[N][N],g[N][N][N];
int main() {
register int n,m,i,j,k,v,maxf;
while (~scanf("%d%d",&n,&m)) {
memset(f,0xf0,sizeof(f));
memset(g,0xf0,sizeof(g));
int ans=-0x7fffffff;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) {
scanf("%d",&f[i][j]);
v=abs(f[i][j]);
maxf=max(g[i-1][j][v+1],g[i][j-1][v+1]);
if (maxf!=0xf0f0f0f0L) f[i][j]-=maxf;
if (ans<f[i][j]) ans=f[i][j];
for (k=100;k>=0;k--) {
g[i][j][k]=max(g[i-1][j][k],g[i][j-1][k]);
g[i][j][k]=max(g[i][j][k],g[i][j][k+1]);
if (k==v&&g[i][j][k]<f[i][j]) g[i][j][k]=f[i][j];
}
}
printf("%d\n",ans);
}
return 0;
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧