P2545 [AHOI2004]实验基地 题解

· · 题解

暴力+最大子段和。

我们可以暴力选择前后的端点，判断中间的实验基地最大可以是多少。

因为第二行是一定的，所以可以用前缀和快速求和。 第一行就是要选出不为头尾的最小的一段，因为上面一段的子段和减去这一段，和就会最大，这样两行加起来就会最大。

#include<bits/stdc++.h>
using namespace std;
int a[2005],b[2005],f[2005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=f[i-1]+a[i];//前缀和
        a[i]=-a[i];//改变正负，这样只要求最大子段和
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        b[i]+=b[i-1];//前缀和
    }
    int s=-1e9;
    for(int i=1;i<=n;i++){
        int x=0,h=-1e9;
        for(int j=i+1;j<n;j++){
            x+=a[j];
            h=max(h,x);//最大字段和
            if(x<0)x=0;
            s=max(s,f[j+1]-f[i-1]+b[j+1]-b[i-1]+h);//第一行的和+第二行的和-第一行最小的一段数字
        }
    }
    cout<<s;
    return 0;
}