题解 P2545 【[AHOI2004]实验基地】

· · 题解

Description

给定一个 2 \times N 的矩阵，求一个凹形块使得这个凹形块里的数字和最大。

Solution For O(n^4)

枚举大长方形，枚举第一行的小长方形，时间复杂度 O(n^4)。

Solution For O(n^2)

我们可以把一个凹形块拆开，比如这样：

---++---+++--    ---++  ---  +++--
---++++++++-- -> ---++  +++  +++--

左边和右边可以做一个最大子段和，每一位计算 a[i][1]+a[i][2]。

然后我们只需要枚举中间块的大小即可。

然后，我们发现这个的数据范围刚好为 2000，所以就过了，但我们还有一种可以过 10^6 的方法。

Solution For O(n)

考虑分类讨论动归，依然是最大子段和，我们都知道最大子段和的动归方程是：

dp[i]=\max\{dp[i-1],0\}+a[i]

看前面的 \max，如果我们采用 dp[i-1]，代表第 i 块接在了第 i-1 块后。

如果是 0，那么代表我们要重新开始一个块。

那么，我们采取这样的思路，对这道题的模型进行分类讨论 —— 讨论怎样接块。

裸的最大子段和，dp1[i]=\max\{dp1[i-1],0\}+a[i][1]+a[i][2]\}。

分为两种情况，第一种是对于一个长方形块后面接一个第二行的小块，第二种是对于一个 \tt L 形块后面接一个第二行的小块，这两种分别做一个最大子段和并取一个 \max，即 dp2[i]=\max\{dp1[i-1],dp2[i-1]\}+a[i][2]。

分为两种情况，第一种是对于一个 \tt L 形后面接一个块，第二种是对于一个凹形快后面接一个块，这两种分别做一个最大子段和并取一个 \max，即 dp3[i]=\max\{dp2[i-1],dp3[i-1]\}+a[i][1]+a[i][2]。

所以我们总和一下这三种情况即可。

Code

#include <bits/stdc++.h>

using namespace std;

int a[2086][3];
int dp1[2086];
int dp2[2086];
int dp3[2086];

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i][1]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i][2]);
    int cnt = 0;
    memset(dp1, -0x3f, sizeof(dp1));
    memset(dp2, -0x3f, sizeof(dp2));
    memset(dp3, -0x3f, sizeof(dp3));
    for (int i = 1; i <= n; i++) {
        dp1[i] = max(dp1[i - 1], 0) + a[i][1] + a[i][2];
        if (i != 1 && i != n) dp2[i] = max(dp1[i - 1], dp2[i - 1]) + a[i][2];
        if (i != 1) dp3[i] = max(dp2[i - 1], dp3[i - 1]) + a[i][1] + a[i][2];
    }
    int Max = -0x3f;
    for (int i = 1; i <= n; i++) Max = max(Max, dp3[i]);
    printf("%d", Max);
    return 0;
}

By Shuchong
2020.10.5