CF1155D Beautiful Array(动态规划)

佚名 6年前 (2019-04-23) 随笔 978人围观抢沙发百度已收录

做法

\(f_{i,0}\)表示以\(i\)结尾未操作时的最大值

\(f_{i,1}\)表示以\(i\)结尾正在操作时的最大值

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

\(f_{i,2}\)表示以\(i\)结尾已结束操作时的最大值

Code

#include<bits/stdc++.h>
typedef long long LL;
const int maxn=1e6+9;
LL ans,n,x;
LL a[maxn],f[maxn][3];
int main(){
    std::cin>>n>>x;
    for(LL i=1;i<=n;++i){
        std::cin>>a[i];
        f[i][0]=std::max(f[i-1][0]+a[i],0LL);
        f[i][1]=std::max(f[i-1][1]+a[i]*x,f[i][0]);
        f[i][2]=std::max(f[i-1][2]+a[i],f[i][1]);
        ans=std::max(ans,f[i][2]);
    }
    std::cout<<ans;
}