题目链接

bzoj3111: [Zjoi2013]蚂蚁寻路

题解

发现走出来的图是一向上的凸起锯齿状

对于每个突出的矩形dp一下就好了

代码

/*
*/
#include<cstdio>
#include<algorithm>
const int maxn = 127;
inline int read() {
 int x = 0,f = 1;
  char c = getchar();
 while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
 while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
 return x * f;
}
const int INF = 0x3f3f3f3f;
const int rp  = 0x7fffffff;
int n,m,k;
int sum[maxn][maxn],a[maxn][maxn];
int g[maxn][25][maxn][2];
int dp[maxn][maxn][maxn];
int main() {
int ans = -0x3f3f3f3f;
n = read(),m = read(),k = read();
k = k << 1 | 1;
for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) a[i][j] = read(), sum[i][j] = sum[i - 1][j] + a[i][j];
for(int i = 1;i <= k;++ i) for(int j = 1;j <= n;++ j)
g[0][i][j][0] = g[0][i][j][1] = dp[0][i][j] = -INF;
for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) {
for(int p = 1;p <= k;++ p) {
for(int h = i;h;-- h)
dp[j][p][h] = std::max(dp[j - 1][p][h],g[j - 1][p - 1][h][p % 2]) - sum[h - 1][j] + sum[i][j];
g[j][p][1][0] = -INF;
for(int h = 2;h <= i;++ h)
g[j][p][h][0] = std::max(dp[j][p][h - 1],g[j][p][h - 1][0]);
g[j][p][i][1] = -INF;
for(int h = i - 1;h;-- h)
g[j][p][h][1] = std::max(dp[j][p][h + 1],g[j][p][h + 1][1]);
}
ans = std::max(ans,std::max(dp[j][k][i],g[j][k][i][0]) );
}
printf("%d\n",ans);
return 0;
}