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

ningyuheng · 2017-09-29 20:55:32 · 题解

//这道题就是一道动态规划的题，枚举开始的位置，后面的位置直接用一道动态规划就过掉了

//ps:详情请看题解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,i,j,a[3][2002],b[2002][2002][3],max1=-2000000000;
int main()
{
    cin>>n;
    for(i=1;i<=2;i++)
        for(j=1;j<=n;j++)
            cin>>a[i][j];//输入 
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
        {
            if(j<n-1)//如果到了第n-1个登陆地带时还没有建造实验基地时就不符合题意 
                b[i][j][0]=b[i][j-1][0]+a[1][j]+a[2][j];//b[i][j][0]表示从i开始到j还没有建实验基地的最多的试用度 
            else
                b[i][j][0]=-2000000000;
            if(j!=i&&j!=n)//如果到第i个登陆地带已经开始建造实验基地或第n个登陆地带时还没有完成建造实验基地时也不符合题意
                b[i][j][1]=max(b[i][j-1][1],b[i][j-1][0])+a[2][j];//b[i][j][1]表示从i开始到j已经开始建造实验基地的最多的试用度
            else
                b[i][j][1]=-2000000000;
            if(j>i+1) //不可能在第i个或第i+1个登录地带就已经建造完成了实验基地
                b[i][j][2]=max(b[i][j-1][2],b[i][j-1][1])+a[1][j]+a[2][j];//b[i][j][2]表示从i开始到j已经建完实验基地的最多的试用度 
            else
                b[i][j][2]=-2000000000;
            max1=max(b[i][j][2],max1);//统计建完了实验基地的最大值 
        }
    cout<<max1<<endl;//输出 
    return 0;
}