[NOIP2000 提高组] 方格取数

题目描述

设有 $N \times N$ 的方格图 $(N \le 9)$，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$。如下图所示（见样例）:

某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$）。
此人从 $A$ 点到 $B$ 点共走两次，试找出 $2$ 条这样的路径，使得取得的数之和为最大。

输入格式

输入的第一行为一个整数 $N$（表示 $N \times N$ 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 $0$ 表示输入结束。

输出格式

只需输出一个整数，表示 $2$ 条路径上取得的最大的和。

样例 #1

样例输入 #1

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

样例输出 #1

67

提示

NOIP 2000 提高组第四题

使用四维的dp，因为这里来说，可以ij当做第一次走过到了的点，kl当做第二次走过到了的点，所以就是

dp[i][j][k][l] = 
//最大值
dp[i-1][j][k-1][l]
dp[i][j-1][k-1][l]
dp[i-1][j][k][l-1]
dp[i][j-1][k][l-1]
//加上本身所到了的a[i][j],a[k][l]
//如果两个是一样的位置，那么只要加一次

ac代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdlib>
#include <queue>
#define LL long long
#define endl "\n"
#define int long long
#define rg register
#define pli pair<LL,int>
#define pil pair<int,LL>
#define debug(x) std:: cout << "---DEBUG--- " << x << " -----DEBUG----\n"
#define rep(a,b,c) for(int i = a; i < b; i += c)
#define repr(a,b,c) for(int i = a; i > b; i -= c)

using namespace std;
int m[100][100];
int dp[50][59][50][50];
signed main() {

    int n;
    int a, b, c;
    cin >> n;
    while(cin >> a >> b >> c){
        if(a == b && a == 0) break;
        m[a][b] = c;

    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                for(int l = 1; l <= n; l++){
                    dp[i][j][k][l] = max(
                                         max(dp[i-1][j][k-1][l], dp[i][j-1][k-1][l]),
                                         max(dp[i-1][j][k][l-1], dp[i][j-1][k][l-1]))
                                         + m[i][j] + m[k][l];
                    if(i == k && j == l) dp[i][j][k][l] -= m[i][j];
                }
            }
        }
    }


    cout << dp[n][n][n][n];


    return 0;
}