Educational Codeforces Round 63-D（基础DP）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：https://codeforces.com/contest/1155/problem/D

题意：给定n个数，可以选择一段连续子段将其乘x，也可以不操作，求最大连续子段和。

思路：比赛时觉得是dp，但怎么也想不出来QAQ，dp太难了。。。赛后看了别人题解，找到状态和转移方程就很简单了，然而比赛时我就是想不到。。。

考虑下标i：有3种情况，可能[0,i]都没有乘x，可能i乘了x，可能[i,n]都不会乘x。分别用dp[i][0]表示以i结尾的最长子段和且 [0,i]都没乘x,dp[i][1]表示以i结尾的最长子段和且i要乘x,dp[i][2]表示以i结尾的最长子段和且[i,n]都不会乘x。

则状态转移方程为：dp[i][0]=max(dp[i-1],0)+a[i];

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

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

加油！！下一次会更好！

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;int n,x;
LL dp[][],ans;int main(){
scanf("%d%d",&n,&x);
for(int i=;i<=n;++i){
LL tmp;
scanf("%lld",&tmp);
dp[i][]=max(dp[i-][],0LL)+tmp;
dp[i][]=max(dp[i-][],max(dp[i-][],0LL))+1LL*tmp*x;
dp[i][]=max(dp[i-][],max(dp[i-][],0LL))+tmp;
ans=max(ans,max(dp[i][],max(dp[i][],dp[i][])));
}
printf("%lld\n",ans);
return ;
}