方阵里面的dp

打了一场luogu的信心赛，惊讶地发现我不会T2，感觉像这样在矩阵里面的dp看起来很套路的样子，但是仔细想想还是有很多需要注意的细节。
又想到之前貌似也考过一些类似的题目 然而我并没有改 ，于是打算补补锅。
目前大概想到几道题，慢慢写吧。

luogu P1006 传纸条 && 小集训模拟赛5 方格取数

很简单的两道题。注意到在“方格取数”中，因为每个方格的数字只能取一次，因此一定不会走重复路线（当然是在所有数字都大于0的情况下）。那就和“传纸条”是同一道题了。
数组可以开4维，3维，貌似还有二维？因为数据范围太小就懒得写优化了。（数据范围大的话貌似就要用网络流了，本Orzer不会）
代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int a[25][25],vis[25][25],dp[25][25][25][25];
void Solve(){
    int n;scanf("%d",&n);
    int o,u,r;
    while(1){
        scanf("%d%d%d",&o,&u,&r);
        if(!o&&!u&&!r) break;
        a[o][u]=r;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
            	for(int x=1;x<=n;++x){
            		if((i+j)!=(k+x)) continue;
            		dp[i][j][k][x]=max(max(dp[i-1][j][k-1][x],dp[i][j-1][k-1][x]),max(dp[i-1][j][k][x-1],dp[i][j-1][k][x-1]));
            		if(i==k) dp[i][j][k][x]+=a[i][j];
            		else dp[i][j][k][x]=dp[i][j][k][x]+a[i][j]+a[k][x];
            	}
            }
        }
    }
    printf("%d",dp[n][n][n][n]);
}
int main(){
    Solve();
    return 0;
}

小集训模拟赛 T2 小象与老鼠

luogu U129493 「EZEC-4.5」走方格（2020.10.4 君のNOIP のCSP信心赛 T2）

小集训模拟赛9 T4 步步为零

方阵里面的dp

原文：https://www.cnblogs.com/wwcdcpyscc/p/13767719.html