Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array 分类讨论连续递推dp

题意：给出一个 数列 和一个x 可以对数列一个连续的部分 每个数乘以x  问该序列可以达到的最大连续序列和是多少

思路： 不是所有区间题目都是线段树！！！！！！

这题其实是一个很简单的dp  

使用的是分类讨论的思想

我们设置dp数组 

dp[1][i] 表示一直没有用x 乘过的数组 必须以i 结尾（i可以不选 也就是空序列）的最大连续和

dp[2][i] 表示i是被x乘过的 必须以i 结尾（i可以不选 也就是空序列）的最大连续和

dp[3][i] 表示i之前的数已经有一段被x乘过了 必须以i 结尾（i可以不选 也就是空序列）的最大连续和

本题需要开ll   

那么就有状态转移方程为    dp[1][i]=max(dp[1][i-1]+a[i],0)   (要么以i结尾向前面选  要么什么都不选)

　　　　　　　　　　　　dp[2][i]=max(dp[1][i-1]+a[i]*x,dp[2][i-1]+a[i]*x,0)    （要么首次开始乘x 要么 是中间或者结尾开始乘）

　　　　　　　　　　　　dp[3][i]=max(dp[3][i-1]+a[i],dp[1][i-1]+a[i],0)  （要没是从上个前面一段已经乘过的直接加a[i],推过来 ，要么是从还没有乘过x 的直接加a[i]推过来）