欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Educational Codeforces Round 63 (Rated for Div. 2)-D

程序员文章站 2022-06-04 08:10:30
...

Educational Codeforces Round 63 (Rated for Div. 2)-D

地址:http://codeforces.com/contest/1155/problem/D

思路:DP

DP1:前缀和+DP

选择区间=左边不改变区间L[i]+中间改变区间+右边不改变区间R[i] (区间可为空) 
L[i]: 前i个元素中以第i元素结尾的不变化区间的最大值 
R[i]: 后n-i个元素中以第i元素开始的不变换区间的最大值 
dp[i]:L[i]+中间改变区间
dp[i]=max{dp[i-1]+x*a[i],L[i]} (即中间区间存在和不存在的情况) 
ans=max{dp[i]+R[i+1]} 

DP2:

dp[i][0]: 前i个元素中以第i元素结尾的不变换区间的最大值
dp[i][1]: 前i个元素中以第i元素结尾的正在变换区间的最大值
dp[i][2]: 前i个元素中以第i元素结尾的已经变换区间的最大值

dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
dp[i][1]=max(dp[i-1][0]+a[i]*x,max(dp[i-1][1]+a[i]*x,a[i]*x));
dp[i][2]=max(dp[i-1][1]+a[i],max(dp[i-1][2]+a[i],a[i]));

 

Code1:

#include<iostream>
using namespace std;
typedef long long LL;

const int MAX_N=3e5+5;
int n,x;
LL ans;
LL a[MAX_N];
LL L[MAX_N],R[MAX_N];
/*
选择区间=左边不改变区间L[i]+中间改变区间+右边不改变区间R[i] (区间可为空) 
L[i]: 前i个元素中以第i元素结尾的不变化区间的最大值 
R[i]: 后n-i个元素中以第i元素开始的不变换区间的最大值 
dp[i]:L[i]+中间改变区间
dp[i]=max{dp[i-1]+x*a[i],L[i]} (即中间区间存在和不存在的情况) 
ans=max{dp[i]+R[i+1]} 
*/

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>x;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	LL Max=0,Min=0,Sum=0;
	for(int i=1;i<=n;++i)
	{
		Sum+=a[i];
		Min=min(Min,Sum);
		L[i]=Sum-Min;
	}
	Min=0,Sum=0;
	for(int i=n;i>=1;--i)
	{
		Sum=Sum+a[i];
		Min=min(Min,Sum);
		R[i]=Sum-Min;
	}
	for(int i=1;i<=n;++i)
	{
		Max=max(Max+x*a[i],L[i]);
		ans=max(ans,Max+R[i+1]);
	}
	cout<<ans<<endl;
	
	return 0;
}

Code2:

#include<iostream>
using namespace std;
typedef long long LL;

const int MAX_N=3e5+5;
int n;
LL a[MAX_N];
LL dp[MAX_N][3];
/*
dp[i][0]: 前i个元素中以第i元素结尾的不变换区间的最大值
dp[i][1]: 前i个元素中以第i元素结尾的正在变换区间的最大值
dp[i][2]: 前i个元素中以第i元素结尾的已经变换区间的最大值

dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
dp[i][1]=max(dp[i-1][0]+a[i]*x,max(dp[i-1][1]+a[i]*x,a[i]*x));
dp[i][2]=max(dp[i-1][1]+a[i],max(dp[i-1][2]+a[i],a[i]));
*/
int main()
{
	ios::sync_with_stdio(false);
    LL x,ans=0;
    cin>>n>>x;
    for(int i=1;i<=n;++i)
		cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<3;j++)
        {
            if(j==0)	dp[i][j]=max(dp[i-1][0]+a[i],a[i]);
            else if(j==1)	dp[i][j]=max(dp[i-1][j-1]+a[i]*x,max(dp[i-1][j]+a[i]*x,a[i]*x));
            else	dp[i][j]=max(dp[i-1][j-1]+a[i],max(dp[i-1][j]+a[i],a[i]));
            ans=max(ans,dp[i][j]);
        }
    cout<<ans<<endl;
    
    return 0;
}

 

相关标签: 算法