方格取数
总时间限制: 1000ms 内存限制: 65536kB
[描述]
设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：< p="">
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。输出只需输出一个整数，表示2条路径上取得的最大的和。
[样例输入]
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
[样例输出]
67
[Solution]
大暴力枚举两条路每个点位置，太暴力了自己看代码吧..
AC代码：
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 int N; 5 int board[20][20]; 6 int dp[20][20][20][20]; 7 int main(){ 8 scanf("%d",&N); 9 while(true){ 10 int a,b,c; scanf("%d%d%d",&a,&b,&c); 11 if(!a&&!b&&!c) break; 12 board[a][b]=c; 13 } 14 for(int i=1;i<=N;++i) 15 for(int j=1;j<=N;++j) 16 for(int k=1;k<=N;++k) 17 for(int p=1;p<=N;++p){ 18 int maxn=max(dp[i-1][j][k-1][p],max(dp[i-1][j][k][p-1],max(dp[i][j-1][k-1][p],dp[i][j-1][k][p-1]))); 19 if(i==k&&j==p) dp[i][j][k][p]=maxn+board[i][j]; 20 else dp[i][j][k][p]=maxn+board[i][j]+board[k][p]; 21 } 22 printf("%d",dp[N][N][N][N]); 23 return 0; 24 }