题解 P1004 【方格取数】
Azuree
2019-08-13 22:41:00
一道典型的棋盘dp。
一共需要走两次，我们不妨同时处理这两条路径。这样，我们既可以方便地处理两条路径重合的情况，也可以减少代码的时间复杂度。
最朴素的想法是开一个四维数组$f[x_1][y_1][x_2][y_2]$表示当两条路径分别处理到$(x_1,y_1)$和$(x_2,y_2)$时能够获得的最大的累积和。但是，四维数组处理起来时间复杂度太大了，所以我们要想办法把它降成三维。
我们可以发现，每当我们走一步，那么x坐标和y坐标之间总会有一个数加$1$。所以，我们可以用k来表示x坐标和y坐标的和，从而通过y坐标来计算出x坐标。由于k对于两条同时处理的路径可以是公共的，所以我们可以用$f[k][y_1][y_2]$来表示当前状态。
特殊的，由于每一个方格的数只可以取一次，所以我们要判断i和j是否相当。
于是，我们就可以得到一个状态转移方程了：
$$f[k][i][j]=max(f[k-1][i][j],f[k-1][i-1][j]f[k-1][i][j-1]f[k-1][i-1][j-1])+[(i==j)?map[k-i+1][i]:map[k-i+1][i] + map[k-j+1][j]]$$
我们可以来看一下我们到底是通过哪些状态转移到当前状态的：
code:
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
int n,m,map[205][205],f[205][205][205],x,y,v;
int cmp(int a,int b,int c,int d)
{
a = max(a,b);
c = max(c,d);
return max(a,c);
}
int main()
{
m = read();
n = m;
x = read(); y = read(); v = read();
while(x > 0)
{
map[x][y] = v;
x = read(); y = read(); v = read();
}
for(int k = 1; k <= m + n; k++)
for(int i = 1; i <= min(k,n); i++)
for(int j = 1; j <= min(k,n); j++)
{
f[k][i][j] = cmp(f[k - 1][i][j],f[k - 1][i - 1][j],f[k - 1][i][j - 1],f[k - 1][i - 1][j - 1]) + map[k - i + 1][i] + map[k - j + 1][j];
if(i == j) f[k][i][j] -= map[k - i + 1][i];
}
f[n + m][n][n] = cmp(f[n + m - 1][n][n - 1],f[n + m - 1][n - 1][n],f[n + m - 1][n][n],f[n + m - 1][n - 1][n - 1]);
printf("%d\n",f[n + m][n][n]);
return 0;
}
```