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 ;
}
上一篇:Eclipse 搭建 Strust2开发环境


下一篇:多个互相有联系的checkbox的单选逻辑