传纸条
传纸条
比较简单的四维棋盘动归，只要能想明白，还是蛮好写的。
题目来源:Luogu
设两个人同时从(0,0)点出发，我们用i,j来表示第一个人的坐标，用k,l表示第二个人的坐标，我们只需要确定两个人不会重叠，然后进行DP就好了。 比如，我们假设(i,j)在(k,l)”上面“，则最终状态为f[n-1][n][n][n-1]，即两个点最终走到了终点的上边和左边。
状态转移方程为: \[ f[i][j][k][l] = a[i][j] + a[k][l] + max(f[i-1][j][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k-1][l],f[i][j-1][k][l-1]) \]
所以，我们有了一个\(O(n^2m^2)\)的算法，最终的代码为： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
int a[52][52];
int f[52][52][52][52];
int Max(int a,int b,int c,int d)
{
truereturn max(max(a,b),max(c,d));
}
int main()
{
truememset(f,0,sizeof(f));
trueint n,m;
truescanf("%d%d",&m,&n);
truefor (int i = 1; i<=m; i++)
truetruefor (int j = 1; j<=n; j++)
truetruetruescanf("%d",&a[i][j]);
true//我们设(i,j)在(k,l)上面
truefor (int i = 1; i<m; i++)
truetruefor (int j = 2; j<=n; j++)
truetruetruefor (int k = i+1; k<=m; k++)
truetruetruetruefor (int l = 1; l<j; l++)
truetruetruetruetruef[i][j][k][l] = a[i][j] + a[k][l] + Max(f[i-1][j][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k-1][l],f[i][j-1][k][l-1]);
trueprintf("%d",f[m-1][n][m][n-1]);
}
但是，我们可以发现一个规律，$ i+j == k+l $,也就是说我们可以用三个变量来表示这两个点的位置。如此，我们便有了f[i][j][k]来表示两点位置，i,j分别为两点的纵坐标，k则为当前i,j之和。因为每次只可能是横坐标或纵坐标加一，所以总步数减去纵坐标即是横坐标。
转移方程为: \[ f[i][j][k] = a[i][k-i] + a[j][k-j] + max(f[i][j][k-1],f[i-1][j][k-1],f[i][j-1][k-1],f[i-1][j-1][k-1]); \]
DP时的循环应为: 1
2
3for (int k = 3; k<n+m; k++) //因为在(1,1)时k已为2，所以这里从3开始
truefor (int i = 1; i<m; i++)
for (int j = i+1; j<=m; j++) //i点在j点上面
最后输出f[m-1][m][n+m-1]即可，代码不再赘述。