洛谷P2545 [AHOI2004]实验基地
? 解题记录 ? ? 洛谷 ? ? 单调栈 ? ? 模拟 ?    2018-10-29 23:30:59    633    0    0

题目描述

输入输出格式

输入格式:

 

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制
4
-1 2 -3 4
5 6 7 8
输出样例#1: 复制
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;
} 

上一篇: 洛谷P4343 [SHOI2015]自动刷题机

下一篇: 洛谷P2439 [SDOI2005]阶梯教室设备利用

633 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航