设有N×N的方格图(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。
某人从图的左上角的AA点出发，可以向下行走，也可以向右走，直到到达右下角的BB点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从（0， 0）点到（n，n）点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入格式：
输入的第一行为一个整数N（表示N×N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
如：
8
6 1 7
3 2 9
2 3 5
1 4 3
3 4 3
6 6 6
1 7 1
0 0 0
输出格式：
输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间
如：
67
找出2条路径之和最大的线路：不妨假设两条路一起走（LineA, LineB）
从图中可见，当前LineA走到点A(i, j)，LineB走到点B(k, l)
假设有一个变量可以描述当前状态，设置这个变量：opt[i][j][k][l]
opt[i][j][k][l] = 上一个状态中，4种情况（TopA, LeftA, TopB, LeftB）中最大的那个值，加上当前两个点（A, B）的值，如果点A和点B重合，则加一个（A或B）的值。
opt[i][j][k][l] = max[TopA, LeftA, TopB, LeftB] + A + B 或 opt[i][j][k][l] = max[TopA, LeftA, TopB, LeftB] + A
// // main.cpp // DP_GetNumberInGrid // // Created on 2018/9/25. // Copyright © 2018 NOIP. All rights reserved. // #include <iostream> using namespace std; int n,i,j,tmp,k,l; int puz[20][20], dp[20][20][20][20]; int main() { scanf("%d",&n); while(scanf("%d%d%d", &i, &j, &tmp) && i) puz[i][j] = tmp; for(i = 1;i <= n; i++) for(j = 1; j <= n; j++) for(k = 1; k <= n; k++) for(l = 1; l <= n; l++) { dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]), max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]))+puz[i][j]; if(i != k||j != l) dp[i][j][k][l] += puz[k][l]; } printf("%d\n", dp[n][n][n][n]); return 0; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。