题目描述
设有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;
}