DP
题目链接：https://www.luogu.org/problem/show?pid=1004
题目大意：
给你一个矩阵，有一些点上有数字，只能向右走或向下走，走过后这个点上的数字会变成0，从左上角到右下角走两次，所能得到的最大数字之和
A:如果不考虑走两次的话，会简单一点，那首先设计状态~
B:f[ i ][ j ] 表示从起点到 i,j 点 所能取得的数字和最大为f[ i ][ j ]
A:然后想想对于每个点他能由哪里直接推出来？
B:因为只能向右或向下，所以他一定是由左边或者上边走过来
A:走过来就加上这个点的数字？
A:然后：
f[i][j] = max(f[i - 1][j],f[i][j - 1]) + mp[i][j];
是这样么？？
B:因为要走两遍，所以跑两次，然后第一次走过的都设成0不就可以了？A:等等等等，两次的最优真的等同于一次同时考虑两个的最优么？？（哈哈哈嗝，就是不告诉你答案~~）
（解释见下文）
END.
对于每一个点，都可以由左边或上边走过来
因为要走两遍所以可以看成是两个同时从左上角开始走
这样的话这样才能确定一种状态呢？
你需要同时知道两个点的坐标,是同时！！
设计状态：f[i][j][a][b] 为第一个点走到i,j 第二个点走到a,b时所能取到的最大数字和
（有5个量，把其中4个确定，另一个作为答案统计）
根据移动的规则，很容易就能推出方程来啦~
f[i][j][a][b] = maxx(f[i - 1][j][a - 1][b],f[i - 1][j][a][b - 1], f[i][j - 1][a][b - 1],f[i][j - 1][a - 1][b]);
那怎么处理走过的情况呢？
因为只能向右走或向下走，
所以a路走到b路已走过的点时，
b路一定也在正这个点上，
也就是说，
他们一定是同时走到相同的点。（自己动手试试啦~）
那我们可以直接判两点是否是同一个点来判断是否走重。
好的，现在该注意的都分析了，
然后。。。贴代码？？
当然不是不是不是！！
还记得小A的问题么（A:记得记得！）
为什么不能看成是两次最优的组合呢？
那是因为在同时考虑两条路时，不仅考虑了一条最优，
还考虑了在这条最优的路线之外还能尽量多的走过多少数字，
而在考虑一条路时，可能会导致本来可以全取走的数没能取完。
看数据看数据：
样例输入： 7 1 3 2 1 4 3 2 3 3 3 3 3 5 5 4 6 5 4 7 3 2 7 5 4 0 0 0 二维DP输出：23 四维DP输出：25 方格示意图： 0 0 2 3 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 5 0 0 0 0 2 0 4 0 0
嗯，这个题就是这样了
Codes:
#include#include #include #include using namespace std;const int N = 10 + 5;int n,mp[N][N];int f[N][N][N][N],bo[N][N];int maxx(int x,int y){ if(x > y) return x; return y;}int main(){ scanf("%d",&n); int a,b,c; for(;;){ scanf("%d%d%d",&a,&b,&c); if(a == b && b == c && c == 0) break; mp[a][b] = c; } for(int i = 1;i <= n;++ i){ for(int j = 1;j <= n;++ j){ for(int a = 1;a <= n;++ a){ for(int b = 1;b <= n;++ b){ f[i][j][a][b] = maxx(f[i - 1][j][a - 1][b],f[i - 1][j][a][b - 1]); f[i][j][a][b] = maxx(f[i][j][a][b],f[i][j - 1][a][b - 1]); f[i][j][a][b] = maxx(f[i][j][a][b],f[i][j - 1][a - 1][b]); if(i == a && j == b) f[i][j][a][b] += mp[i][j]; else f[i][j][a][b] += mp[i][j] + mp[a][b]; /* else if(!bo[i][j] || !bo[a][b]){ //之前的错误判法 if(!bo[i][j]){ f[i][j][a][b] += mp[i][j]; } if(!bo[a][b]){ f[i][j][a][b] += mp[a][b]; } bo[i][j] = bo[a][b] = 1; }*/ // cout << f[i][j][a][b] << '\n'; } } } } cout << f[n][n][n][n] << '\n'; return 0;}
MAS:
考虑思路的正确性？（好吧这很重要）
不会写就加维度？