Rockdu's Blog

题目描述

输入输出格式

输入格式：

第一行有一个整数N(3<N<2000)，表示登陆地带的大小是2×N。随后的两行每一行有N个整数（其绝对值不超过10^6），表示对应的矩形土地的适用度评估值，各个整数之间用一个空格隔开。

输出格式：

只有一行输出，为整数M，即所确定的实验基地的适用度。

输入输出样例

4
-1 2 -3 4
5 6 7 8

31​

不知道为什么N会是2000而不是10^6。

这道题的O(n)做法很显然。考虑把"凹"形拆成两个同时选择两行的区间中间夹一个只选择下面一行的区间，这样我们首先可以对所有的点p处理出它向左/向右延伸的最大权值的选择两行的区间，分别记为L[i]，R[i]。这时我们已经可以O(n^2)枚举中间只选择下面一行的区间，O(1)统计答案了。

但实际上我们可以更优秀，考虑一个只选择下面一行的区间的答案，是R[r] + L[l] + sum[r-1] - sum[l]。其中sum是下一行的前缀和。

考虑r一定的情况下，我们只需要知道f[l]=L[l]-sum[l]的最小值就行了，这个用单调栈维护即可。

我懒写了个O(n^2)...

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2e3 + 5;
LL num[maxn], down[maxn], L[maxn], R[maxn], ans;
int n;

int main() {
    scanf("%d", &n);
    For(i, 1, n) scanf("%lld", &num[i]);
    For(i, 1, n) scanf("%lld", &down[i]), num[i] += down[i];
    For(i, 1, n) num[i] += num[i - 1], down[i] += down[i - 1];
    memset(R, -0x3f, sizeof(R));
    memset(L, -0x3f, sizeof(L));
    ans = -0x3f3f3f3f3f3f3f3f;
    For(i, 1, n) For(j, i, n) {
        R[i] = max(R[i], num[j] - num[i - 1]);
    }
    For(i, 1, n) For(j, 1, i) {
        L[i] = max(L[i], num[i] - num[j - 1]);
    }
    For(i, 1, n) For(j, i + 2, n)
        ans = max(ans, L[i] + R[j] + down[j - 1] - down[i]);
    printf("%lld", ans);
    return 0;
}