自动搬运

查看原文

来自洛谷，原作者为

	卷王 可惜没如果.

搬运于2025-08-24 22:28:15，当前版本为作者最后更新于2023-03-26 17:25:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

略。

思路

这题挺难的！

观察数据范围，发现 $O(n^3)$ 最适合，于是选择暴力 dp。

设 $dp_{i,j,0/1}$ 表示当前走到了第 $i$ 行，第 $j$ 列没交换/交换数字的最大权值和。

我们发现蜂窝图的行和列都是 $2 × n - 1$，所以得开 $dp[200][200][2]$。有点烦人的是输入，但是找一下规律其实也没那么难。主要是先输入上半部分，再输入下半部分：

for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n + i - 1; j++) {
			cin >> a[i][j];
		}
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j <= 2 * n - i - 1; j++) {
			cin >> a[i + n][j];
		}

然后我们来讨论一下状态转移方程。

转移方程主要分成两种情况（为了方便，数组就不用 $\LaTeX$ 了）：

• 从第 $1$ 行到第 $n$ 行（列数递增），易得转移方程：$dp[i][j][0] = \max(dp[i-1][j][0],dp[i-1][j-1][0])+a[i][j]$，$dp[i][j][1] = \max(\max(dp[i-1][j][1],dp[i-1][j-1][1])+a[i][j]),\max(dp[i-1][j][0],dp[i-1][j-1][0])+rowmax[i])$。

• 从第 $n + 1$ 行到第 $2 × n - 1$ 行（列数递减），状态转移方程跟上面的没啥两样，建议自己想，实在想不出来看这。

这里面的 $rowmax_i$ 表示第 $i$ 行最大的值。我们用贪心，如果这一行要换值，那么就把值换成最大的。

最后取 $dp_{n×2-1,i,1}$ 的最大值即可。

#include <bits/stdc++.h>
using namespace std;
int n, ans = 0;
int row[207];
int a[207][207];
int dp[207][207][2];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n + i - 1; j++) {
			cin >> a[i][j];
			row[i] = max(row[i], a[i][j]);
		}
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j <= 2 * n - i - 1; j++) {
			cin >> a[i + n][j];
			row[i + n] = max(row[i + n], a[i + n][j]);
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n + i - 1; j++) {
			dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][0]) + a[i][j];
			dp[i][j][1] = max(max(dp[i - 1][j][1], dp[i - 1][j - 1][1]) + a[i][j], max(dp[i - 1][j][0], dp[i - 1][j - 1][0]) + row[i]);
		}
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j <= 2 * n - i - 1; j++) {
			int w = i + n;
			dp[w][j][0] = max(dp[w - 1][j][0], dp[w - 1][j + 1][0]) + a[w][j];
			dp[w][j][1] = max(max(dp[w - 1][j][1], dp[w - 1][j + 1][1]) + a[w][j], max(dp[w - 1][j][0], dp[w - 1][j + 1][0]) + row[w]);
		}
	for(int i = 1; i <= n; i++)
		ans = max(ans, dp[n * 2 - 1][i][1]);
	cout << ans;
	return 0;
}