题解：P1004 [NOIP2000 提高组] 方格取数

· · 题解

一道有点难度的 DP 题......

题目大意

有一个 n \times n 的方格图，每个格子都有一个对应的权值 a_{i,j} ，你从 (1, 1) 开始走，每次可以从 (i, j) 走到 (i + 1, j) 或 (i, j + 1)，最终走到 (n, n)，你需要这样走两次，求你所经过的格子上的权值之和的最大值，每个格子上的权值只计算一次。

题目分析

  1. 状态：定义一个四维数组 f，f_{i\ j\ k\ l} 表示第一次走到第 i 行，第 j 列，第二次到达第 k 行，第 l 列能获得的最大值。

  2. 状态转移方程：我们要考虑以下四种情况：

那么我们就要取这四种情况的最大值了，即：f_{i\ j\ k\ l} = \max\{f_{i-1\ j\ k-1\ l}, f_{i-1\ j\ k\ l-1}, f_{i\ j-1\ k-1\ l}, f_{i\ j-1\ k\ l-1}\}+a_{i\ j}+a_{k\ l}。

但要注意的是，如果 (i, j)=(k,l)，那么就只能加其中一个（不能重复），所以此时要在原来的基础上减去一个 a_{i\ j}。

  1. 初始化：刚开始也就是到点 (1, 1) 能获得的最大值，即 f_{1\ 1\ 1\ 1} = 0。

  2. 答案：由于我们要求第一次和第二次走到右下角的最大值，所以我们的答案为 f_{n\ n\ n\ n}。

上代码：

#include <bits/stdc++.h> 
using namespace std;

int n, x, y, w, a[35][35], f[35][35][35][35]; //表示第一次走到第i行，第j列，第二次到达第k行，第l列能获得的最大值。
int main() {
    cin >> n;
    while(cin >> x >> y >> w) { //输入 
        if(x == 0 && y == 0 && w == 0) break; //退出 
        a[x][y] = w;
    }
    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++) {
                    int t1 = max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]); //记录 
                    int t2 = max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1]); //记录 
                    f[i][j][k][l] = max(t1, t2) + a[i][j] + a[k][l]; //求最大值 
                    if(i == k && j == l) f[i][j][k][l] -= a[i][j]; //如果位置相同，则减去其中一个 
                }
    cout << f[n][n][n][n] << endl; //答案 
    return 0;
}

最后，看在本蒟蒻这么努力的份上，请点个赞吧！球球啦！