codeforces-Ed63-D

codeforces-Ed63-D

七月 08, 2020

D. Beautiful Array

题意
给一串数组

要求最多选一个连续子串乘x

问形成新的数组的最大连续子串和(子串可以为空)

题解

把整个序列分成三段来dp。

dp[0]表示没有乘过x序列的最大值。

dp[1]表示正在乘x的序列的最大值。

dp[2]表示已经乘完x的序列的最大值。

则dp[0]=max(dp[0],dp[0]+val);

dp[1]=max(dp[0],dp[1]+x*val);

dp[2]=max(dp[1],dp[2]+val);

版本1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# include <bits/stdc++.h>

# define maxn 300005

using namespace std;
typedef long long ll;
ll dp[3];
int main()
{
    int n;
    ll m,res=-1e18;
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;++i)
    {
        ll x;
        scanf("%lld",&x);
        dp[0]=max(0ll,dp[0]+x);
        dp[1]=max(dp[0],dp[1]+x*m); ///以当前数作为乘m的子串的起始或不作为起始继承dp[0]
        dp[2]=max(dp[1],dp[2]+x);///以当前数作为乘m的子串的结束之后第一个或作为乘m的子串的最后一个继承dp[1]
        res=max(res,dp[2]);
    }
    cout<<res<<endl;
    return 0;
}

版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll dp[3][(int)3e5+5];
int main(){
    int n,x;cin>>n>>x;ll ans=0;
    for(int i=1;i<=n;i++){
        ll a;cin>>a;
        dp[0][i]=max(dp[0][i-1]+a,0ll);
        ans=max(ans,dp[0][i]);
        dp[1][i]=max(dp[0][i-1],dp[1][i-1])+x*a;
        ans=max(ans,dp[1][i]);
        dp[2][i]=max(dp[2][i-1],dp[1][i-1])+a;
        ans=max(ans,dp[2][i]);
    }
    cout<<ans<<endl;
}