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

Adove · 2018-10-31 22:02:07 · 题解

此题要求max(矩形值-上方最小连续子序列和)

我们枚举左右端点从左往右扫

观察到最小连续子序列和可以借助上一个位置的答案

于是我们就可以\Theta (n^2)求解了

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=3005;

int n,ans;
int a[2][MAXN];
int f[MAXN][MAXN];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[1][i]);
    for(int i=1;i<=n;++i) scanf("%d",&a[0][i]);
    for(int i=1;i<=n-2;++i){
        int ct=0,minn=0x7fffffff,sum=a[1][i+1]+a[1][i]+a[0][i]+a[0][i+1];
        for(int j=i+2;j<=n;++j){
            ct=min(ct,0);
            ct+=a[1][j-1];minn=min(minn,ct);
            sum+=a[0][j]+a[1][j];
            ans=max(ans,sum-minn);
        }
    }printf("%d\n",ans);
    return 0;
}