用简单的搜索，之前听了从清北写的，一直没写博客，现在补上
这两个题实际上是一样的，传纸条虽然有一个是倒着传，其实和正着传是一样的，所以是一样的
就是用一个四维数组，记下两个点的坐标，两个点都可以向上或向下走，所以可以转移到四种情况，就是我下面分的四种
还可以用动归
动态转移方程是
dp[x][y][x2][y2]=max(dp[x][y-1][x2][y2-1],dp[x-1][y][x2][y2-1],dp[x][y-1][x2-1][y2],dp[x-1][y][x2-1][y2])+a[x][y]+a[x2][y2]-(x==x2&&y==y2)*a[x][y];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
35
36
37
38#include<cstdio>
#include<iostream>
using namespace std;
int m,n;
int a[55][55];
int dp[55][55][55][55];
int ans=0;
int dfs(int x,int y,int x2,int y2)
{
if(x==n&&y==n) {return 0;}
if(x<n&&x2<n)
dp[x][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x+1][y][x2+1][y2]?dp[x+1][y][x2+1][y2]:
dfs(x+1,y,x2+1,y2))+a[x+1][y]+a[x2+1][y2]-(x+1==x2+1&&y==y2)*a[x+1][y]);
if(x<n&&y2<n)
dp[x][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x+1][y][x2][y2+1]?dp[x+1][y][x2][y2+1]:
dfs(x+1,y,x2,y2+1))+a[x+1][y]+a[x2][y2+1]-(x+1==x2&&y==y2+1)*a[x+1][y]);
if(y<n&&x2<n)
dp[x][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x][y+1][x2+1][y2]?dp[x][y+1][x2+1][y2]:
dfs(x,y+1,x2+1,y2))+a[x][y+1]+a[x2+1][y2]-(x==x2+1&&y+1==y2)*a[x][y+1]);
if(y<n&&y2<n)
dp[x][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x][y+1][x2][y2+1]?dp[x][y+1][x2][y2+1]:
dfs(x,y+1,x2,y2+1))+a[x][y+1]+a[x2][y2+1]-(x==x2&&y+1==y2+1)*a[x][y+1]);
return dp[x][y][x2][y2];
}
int main()
{
scanf("%d",&n);int x,y,z;
while(~scanf("%d%d%d",&x,&y,&z)){
if(x==0&&y==0&&z==0)
{
break;
}
a[x][y]=z;
}
printf("%d",dfs(1,1,1,1)+a[1][1]);
return 0;
}
1 | #include<cstdio> |