题解 P1004 【方格取数】

我也来发一发！！！这题和传纸条很像哦！ ------------------------------------------------------------------------------------------------------------------------------------------------- **一级** 显然，用f[i][j][k][l]表示第一个人走到(i,j)，第二个人走到(k,l)的最优解，因为楼下讲了太多，我就不再赘述了。发个代码。 ------------------------------------------------------------------------------------------------------------------------------------------------- ```cpp #include<cstdio> #include<algorithm> using namespace std; struct point { int x,y,data; }p[100]; int n,m,map[11][11],f[11][11][11][11]; int main() { int i,j,k,l; scanf("%d",&n); while(1) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(!a&&!b&&!c) break; p[++m].x=a; p[m].y=b; p[m].data=c; } for(i=1;i<=m;i++) map[p[i].x][p[i].y]=p[i].data; for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) { l=i+j-k; if(l<=0) break; f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))); if(i==k&&j==l) f[i][j][k][l]+=map[i][j]; else f[i][j][k][l]+=map[i][j]+map[k][l]; } printf("%d\n",f[n][n][n][n]); return 0; ``` }//改代码的注释我不写了，应该能看懂 ------------------------------------------------------------------------------------------------------------------------------------------------- **二级** 然而这题数据太弱，范围这么小偶也没想到，但是钻研的精神很可贵，还是要多想想。 像楼下说的，用三维数组，优化空间。可以用路径长度代表阶段 f(l,i,ii)表示当前路径长度为l（也就是说当前是第l个状态），第一个人走到(i,l-i)的位置，第二个人走到(ii,l-ii)的位置。 具体原因楼下同样讲得太多了，因为后面还有料，现在就不多说了。 ------------------------------------------------------------------------------------------------------------------------------------------------- **三级** 看过楼下题解的同学应该能够发现，每一次的状态转移都只和上一个阶段有关，即第l-1个阶段。 所以说可以用滚动数组，只记录当前阶段和2的余数的阶段即可。 若l%2==0，则上一个状态l%2==1。反之亦然。 这样空间复杂度从O(n^4)->O(n^3)->O(2n^2) ------------------------------------------------------------------------------------------------------------------------------------------------- **四级** 其实这样已经差不多了，但是还可以继续优化。 如果对01背包的以为写法非常熟悉的话...... 可以模仿，枚举i和ii的时候，如果倒着做，那么当前的值就是上一个阶段的值，连滚动数组都不用。 空间复杂度再降到O(n^2) 贴上四级的代码~~~ ------------------------------------------------------------------------------------------------------------------------------------------------- ```cpp #include<cstdio> #include<algorithm> using namespace std; struct point { int x,y,data;//记录每个点的位置和数值 }p[100]; int n,m,map[11][11],f[11][11]; int main() { int i,ii,j,jj,l; scanf("%d",&n); while(1) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(!a&&!b&&!c) break; p[++m].x=a; p[m].y=b; p[m].data=c; } for(i=1;i<=m;i++) map[p[i].x][p[i].y]=p[i].data; for(l=2;l<=n*2;l++)//每个点最少横着竖着都走一格，最多都走n格就到终点 for(i=l-1;i>=1;i--)//和前面说的一样，倒着做 for(ii=l-1;ii>=1;ii--) { j=l-i;jj=l-ii;//i+j=ii+jj=l f[i][ii]=max(max(f[i][ii],f[i-1][ii-1]),max(f[i-1][ii],f[i][ii-1]))+map[i][j]; //重点说明一下吧，这里省略了很多。如果i不减1，意思就是j-1，因为上一个阶段就是l-1嘛。如果ii-1，意思就是说jj不减1。 f[i][ii]+=map[ii][jj]*(i!=ii); //如果i==ii，其实就是(i==ii&&j==jj)，因为和都是l嘛。如果走过一遍，第二遍走得到的值就是0（题目上说的）。 } printf("%d\n",f[n][n]); //输出意思是在路径长度为2*n的阶段，两遍都走到(n,n)的最优值。因为在这里(j=2*n-i=n,jj=2*n-ii=n),所以走到的就是(n,n)的位置 return 0; } ``` ------------------------------------------------------------------------------------------------------------------------------------------------- OVER ! 一个小小的建议，如果你想对这种两边一起做的DP有更深入的了解，可以做：传纸条和回文的路径 后者很难！！！