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

z2415445508 · 2017-10-11 20:07:53 · 题解

好像还没有题解用的是二维，果断来一发。

理解一下题意，实际上我们要求的就是一个U型的最大得分，而整个矩形都只有两行：岂不是喜滋滋？

深入理解一下：既然是求最大得分，即第一行的中间有连续部分不取，而第二行的底座必须都取，那不是就是在提醒我们要用前缀和解题更加轻便快捷吗！！！！！

也就是提前把以i，j为端点的左右前缀和处理出来，再枚举一下哪一个点不取是最优解，那么不就是正解了吗。

状态转移方程：ans = max{ l[i] + r[j] + x[j-1] - x[i] } (1 <= i < j - 1 <= n - 1);

思路完毕，下面上代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>//头文件库不推荐使用万能头文件,map之类的变量名容易引发错误
using namespace std;
const int MAXM = 2050;
typedef long long int lolo;
lolo n,l[MAXM],r[MAXM],ans,sumup[MAXM],sumdown[MAXM];
lolo up[MAXM],down[MAXM],sum[MAXM];
int main()
{
    std::ios::sync_with_stdio(false);//关闭cin与stdio的同步，效率比scanf快。
    cin>>n;
    for (int i=1;i<=n;i++)    cin>>up[i],sumup[i]=sumup[i-1]+up[i];//实际上up和down两个数组没必要，但是便于理解
    for (int i=1;i<=n;i++)    cin>>down[i],sumdown[i]=sumdown[i-1]+down[i];
    for (int i=1;i<=n;i++)    sum[i] = sumdown[i]+sumup[i];//求出整个的前缀和。
    memset(l,128,sizeof(l));//127为极大值，128为极小值
    memset(r,128,sizeof(r));
    for (int i=1;i<=n;i++)
        for (int j=0;j<=i-1;j++)
            l[i] = max(l[i],sum[i]-sum[j]);//处理出左边(l可理解为left)的上下两部分的前缀和
    for(int i=n-1; i >= 0; i --)
        for(int j=n; j >= i + 1;j --)
            r[i + 1] = max(r[i + 1],sum[j] - sum[i]);//处理出Right的上下两部分的前缀和
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
               if(l[i-1]>0&&r[j+1]>0)
                ans=max(ans,sumdown[j]-sumdown[i-1]+l[i-1]+r[j+1]);//既要包括右边和左边的所有部分，又要让上面有空缺（需要长得像U）
    printf("%d",ans);
}
//有问题可私信