首页 > 代码库 > 【noi 2.6_8786】方格取数（DP+优化）
【noi 2.6_8786】方格取数（DP+优化）
题意：N*N的方格图每格有一个数值，要求从左上角每步往右或往下走到右下角，问走2次的最大和。
解法：走一次的很好想，而走2次，不可误以为先找到最大和的路，再找剩下的最大和的路就是正解。而应该认清动态规划的实质，定义为最佳解的状态，因此要走的2次都要涵括。
O(n^4)——f[i][j][k][l]表示分别走到(i,j)和(k,l)的最大和。每次从上一步分别走(下,下),(右,右),(右,下),(下,右)的状态推导就好了。f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i][j-1][k][l-1],f[i][j-1][k-1][l],f[i-1][j][k][l-1])+a[i][j]+a[k][l]-((i==j&&k==l)?a[k][l]:0);
这样定义感觉很累赘，表示的是2次分别走可相同或不相同步数到相应坐标的状态。可以用同时走k步来定义状态，而且仔细想想，我们可以进一步思考出：由于只能往下和往右走，那么我们根据走到的坐标就可以知道总共和向下、向右各走了几步。反之，若已知总步数和向右走了几步，坐标也是可以知道的了。
于是可以这样定义状态：
O(n^3)——f[k][i][j]表示走k步2次同时各向右走了i步和j步的最大和。也是每次从上一步推。
注意——不能重复算同一格上的数。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 int a[12][12],f[24][12][12]; 8 int mmax(int x,int y) {return x>y?x:y;} 9 int mmin(int x,int y) {return x<y?x:y;}10 int main()11 {12 int n;13 scanf("%d",&n);14 memset(a,0,sizeof(a));15 while (1)16 {17 int x,y,d;18 scanf("%d%d%d",&x,&y,&d);19 if (!x&&!y&&!d) break;20 a[x][y]=d;21 }22 memset(f,0,sizeof(f));23 for (int k=1;k<=2*n;k++)24 for (int i=1;i<=k;i++)25 for (int j=1;j<=k;j++)26 {27 int mx=0,t;28 mx=mmax(mx,f[k-1][i-1][j]);29 mx=mmax(mx,f[k-1][i][j-1]);30 mx=mmax(mx,f[k-1][i-1][j-1]);31 mx=mmax(mx,f[k-1][i][j]);32 if (i==j) t=a[k-i+1][i];33 else t=a[k-i+1][i]+a[k-j+1][j];34 f[k][i][j]=mx+t;35 }36 printf("%d",f[2*n][n][n]);37 return 0;38 }
【noi 2.6_8786】方格取数（DP+优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。