P7266 [BalticOI 2000] Honeycomb Problem 的题解

卷王 · 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;
}