Educational Codeforces Round 63 (Rated for Div. 2)-D
程序员文章站
2022-06-04 08:10:30
...
地址: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;
}
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
Educational Codeforces Round 60 (Rated for Div. 2) ----A - Best Subsegment(思维题)
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
Codeforces Round #619 (Div. 2) D. Time to Run
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
-
【解题报告】Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)
-
Codeforces Round #583 (Div. 1 + Div. 2,) D. Treasure Island(dfs+思维)