2056 - 方格取数
设有N*N的方格图(N<=10我们将其中的某些方格中填入正整数而其他的方格中则放入数字0。如下图所示（见样例）：
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
Input
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
Output
只需输出一个整数，表示2条路径上取得的最大的和。
Examples
Input
8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0
Output
67
Solution C
#include <stdio.h> #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b int main() { int map[11][11]={0},f[11][11]={0}; int i,j,k,N,t; scanf("%d",&N); while (scanf("%d%d%d",&i,&j,&k)&&(i||j||k)) map[i][j]=k; for (i=2;i<=2*N;i++) for (t=min(i,N),j=t;j>0;j--) for (k=t;k>0;k--) { f[j][k]=max(f[j][k],f[j-1][k-1]); f[j][k]=max(f[j][k],f[j][k-1]); f[j][k]=max(f[j][k],f[j-1][k]); if (j==k) f[j][k]+=map[j][i-j]; else f[j][k]+=map[j][i-j]+map[k][i-k]; } printf("%d",f[N][N]); return 0; }
Solution C++
#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; }