题目链接：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
     
      #include
      
       using namespace std;typedef long long LL;int n,x;LL dp[300005][3],ans;int main(){    scanf("%d%d",&n,&x);    for(int i=1;i<=n;++i){        LL tmp;        scanf("%lld",&tmp);        dp[i][0]=max(dp[i-1][0],0LL)+tmp;        dp[i][1]=max(dp[i-1][0],max(dp[i-1][1],0LL))+1LL*tmp*x;        dp[i][2]=max(dp[i-1][1],max(dp[i-1][2],0LL))+tmp;        ans=max(ans,max(dp[i][0],max(dp[i][1],dp[i][2])));    }    printf("%lld\n",ans);    return 0;}