题解 CF1155D 【Beautiful Array】

发表于 | 更新于

$Description$

给定一个值$x$,一个长度为$n$的数组$a$，你可以选择一段区间，让这段区间每个数都乘上$x$,求最大连续子段和

$Solution:$

三个数组,$f_{i}$表示以$i$结尾的最大子段和,$g_{i}$表示选定区间还未完结($a_{i}$乘上$x$)的最大子段和，$h_{i}$表示已经选定区间已经在$1$~$(i-1)$中一处结尾$(a_{i}$不乘$x)$

$f_{i}=max(f_{i-1},0)+a_{i}$

$g_{i}=max(g_{i-1},f_{i-1},0)+a_{i}\times x$

$h_{i}=max(h_{i-1},g_{i-1},0)+a_{i}$

$ans=max(h_{i},g_{i})$

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
signed main(){
    int n=read(),m=read(),ans=0,a,f=0,g=0,h=0;
    for (int i=1;i<=n;++i)
        a=read(),h=max(h,max(g,0ll))+a,g=max(g,max(0ll,f))+a*m,f=max(f,0ll)+a,ans=max(ans,max(h,max(f,g)));
    cout<<ans;
    return 0;
}