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

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

题目大意

有一个

n \times n

的方格图，每个格子都有一个对应的权值

a_{i,j}

，你从

(1, 1)

开始走，每次可以从

(i, j)

走到

(i + 1, j)

或

(i, j + 1)

，最终走到

(n, n)

，你需要这样走两次，求你所经过的格子上的权值之和的最大值，每个格子上的权值只计算一次。

题目分析

状态：定义一个四维数组 $f$ ， $f_{i\ j\ k\ l}$ 表示第一次走到第 $i$ 行，第 $j$ 列，第二次到达第 $k$ 行，第 $l$ 列能获得的最大值。
状态转移方程：我们要考虑以下四种情况：

第一次从左边过来，第二次从左边过来
第一次从左边过来，第二次从上边过来
第一次从上边过来，第二次从左边过来
第一次从上边过来，第二次从上边过来

那么我们就要取这四种情况的最大值了，即：

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)$ 能获得的最大值，即 $f_{1\ 1\ 1\ 1} = 0$ 。
答案：由于我们要求第一次和第二次走到右下角的最大值，所以我们的答案为 $f_{n\ n\ n\ n}$ 。

上代码：

CPP

#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;
}

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

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

文章操作

题目大意

题目分析

相关推荐

评论

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