【洛谷P1004】方格取数

本文主要是介绍【洛谷P1004】方格取数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://www.luogu.org/problem/show?pid=1004

这是一道很经典的多进程动态规划题

一个自然的想法是：贪心地将前面的取过的数全赋成0，然后再取一次，然而并不对（QAQ）

第一次取的显然是最大值，但第二次取的未必是次大值，所以两条非最大的路，也许比一条最大加一条小一点的路更优。

动态规划里的一个重要思想就是，当前的状态无法表示时，可以增添一维来表示

用F[i][j][k][l]表示两次分别走到（i，j）和（k，l）能取到的最大值
a[i][j]表示( i , j )的点值，可以得到DP方程

f[i][j][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])+a[i][j]+a[k][l]；
                  (i!=k&&j!=l)

但实际上i，j，k，l是存在一定的线性关系的，即i+j=k+l，所以可以减掉一维，主要是为了防止空间爆掉（见【传纸条】）
贴代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[50][50][50][50];
int a[50][50];
int main()
{int n;scanf("%d",&n);int aa,bb,cc;while(scanf("%d%d%d",&aa,&bb,&cc)==3)if(aa==0&&bb==0&&cc==0) break;else a[aa][bb]=cc;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)for(int l=1;l<=n;l++){int r1=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]);int r2=max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]);f[i][j][k][l]=max(r1,r2)+a[i][j];if(i!=k&&j!=l) f[i][j][k][l]+=a[k][l];}           printf("%d",f[n][n][n][n]);
}

这篇关于【洛谷P1004】方格取数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---