传纸条：https://www.luogu.org/problemnew/show/P1006
方格取数：https://www.luogu.org/problemnew/show/P1004
这两道题一样的……所以我放在一起整理
方格取数比较简单，记住一条公式，方格任意一点：i+j=k+2。对于这道题，因为开始从左上角走，所以k是走的步数，所以我们只需要一个三维dp，f[k][i][j]表示走了k步，第一个人在第i列，第二个人在第j列，然后根据公式，横坐标也推出来了，所以复杂度只是三次方！然后对于取完数变0这个操作，只需要当横纵坐标都相等时，只取一个就行了。
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> int a[15][15],f[15<<1][15][15],n; using namespace std; int main() { cin>>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; } f[0][1][1]=a[1][1]; for(int k=1;k<=2*n-2;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int x=k+2-i,y=k+2-j; if(x<1||j<1)continue;//判越界 f[k][i][j]=max(f[k-1][i][j],max(f[k-1][i-1][j],max(f[k-1][i][j-1],f[k-1][i-1][j-1])))+a[i][x]+a[j][y]; if(i==j&&x==y)f[k][i][j]-=a[i][x]; } } } cout<<f[2*n-2][n][n]; }
传纸条代码其实差不多的，基本思路也就像上面那个一样。但是它多了一个条件，就是走过了一个格子，另一个人是不能再走的，相当于封路了。这个时候我们要把列强制不相等吗？其实不是的，像上面那样，走到一起就减去就好了。为什么可以这样呢？
https://www.luogu.org/discuss/show?postid=63900
引用了luogu的xeonz1的讨论发言
#include <iostream> #include <cstring> #include <cstdio> #define maxn 55 using namespace std; int f[2 * maxn][maxn][maxn]; int a[maxn][maxn]; int n,m; int max_ele(int a,int b,int c,int d){ if (b>a) a = b; if (c>a) a = c; if (d>a) a = d; return a; } int main(){ cin >> n >> m; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin >> a[i][j]; for (int k=1;k<=n+m-1;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ int xx=k-i+2,yy=k-j+2; if (k-i+2<1 || k-j+2<1) //这里是判断纵坐标的合法性，如果纵坐标不合法那就跳过去 continue; f[k][i][j] = max_ele(f[k-1][i][j],f[k-1][i-1][j-1],f[k-1][i][j-1],f[k-1][i-1][j]) + a[i][xx] + a[j][yy]; if (i==j&&xx==yy) //判断重合路径 f[k][i][j]-=a[i][xx]; } cout << f[n+m-2][n][n] << endl; return 0; }
