[NOIP题目] - 方格取数

方格取数.png

题目描述

设有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;
}