CodeForces-1155D Beautiful Array

比眉伴天荒 2022-01-05 13:49 197阅读 0赞

题目传送门：[CodeForces-1155D Beautiful Array][][  
][Link 1]

### 题目大意： ###

数组的美值是此数组的某个连续子数组的最大总和（此子数组可能为空），现在存在一个有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;
    }

转载于:https://www.cnblogs.com/LjwCarrot/p/10758968.html

[CodeForces-1155D Beautiful Array]: http://codeforces.com/contest/1155/problem/D
[Link 1]: http://poj.org/problem?id=1679