CodeForces-1155D Beautiful Array-蒲公英云

CodeForces-1155D Beautiful Array

题目传送门：CodeForces-1155D Beautiful Array

题目大意：

数组的美值是此数组的某个连续子数组的最大总和（此子数组可能为空），现在存在一个有n个数的

数组，同时拥有一个数x，你能够选择该数组的某个子段乘于x，求出该数组美值得最大值。

分析：

定义三个dp数组:dp1[]、dp2[]、dp3[]

其中 dp1[i] 表示以a[i]结尾的最大子段和

　　dp2[i]表示以a[i]*x结尾的最大子段和

　　dp3[i]表示以a[i]结尾，且a[i]前存在一个区间的数组 * x，该情况下的最大子段和

转移方程：dp1[i] = a[i] + (dp1[i-1] > 0 ? dp1[i-1] : 0)

　　　　 dp2[i] = a[i] * x + max(max(dp1[i-1] , dp2[i-1]),0)

　　 dp3[i] = a[i] + max(dp2[i-1] , dp3[i-1]).

结果则为三个dp数组中的最大值。

代码：

#include<iostream>
using namespace std;
typedef long long ll;
ll dp1[300009],dp2[300009],dp3[300009];
ll n,x,a[300009];
int main()
{
    cin>>n>>x;
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll ans=0;
    dp1[0]=a[0];
    for(int i=1;i<n;i++){                //以a[i]为结尾最大子段和 
        dp1[i]=a[i]+(dp1[i-1]>0?dp1[i-1]:0);
    }
    dp2[0]=a[0]*x;    
    for(int i=1;i<n;i++){                //以a[i]*k为结尾最大子段和 
        dp2[i]=a[i]*x+max(max(dp1[i-1],dp2[i-1]),(ll)0);
    }
    dp3[1]=a[1]+a[0]*x;
    for(int i=2;i<n;i++){                //以a[i]为结尾，a[i]前存在子段*x的最大子段和 
        dp3[i]=a[i]+max(dp2[i-1],dp3[i-1]);
    } 
    for(int i=0;i<n;i++){
        ans=max(max(dp1[i],ans),max(dp2[i],dp3[i]));
    }
    cout<<ans<<endl;
    return 0;
}