Educational CF Round 63 (Div. 2)___D. Beautiful Array （dp）

题目链接：点我啊╭(╯^╰)╮

题目大意：

     比最大子串和多给了个 $x$，可以使至多任意一个子串全部 $\ast x$ ，然后再求最大子串和

解题思路：

    dp思路，懒得讲，只是为了记录一下这个东西

代码思路：

    因为没有其他操作，在遍历的过程中求最大值就行了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
ll dp[maxn][3], a[maxn];

int main(){
	ll n, x;
	scanf("%lld%lld", &n, &x);
	for(int i=1; i<=n; i++) scanf("%lld", a+i);
	ll ans = 0;
	for(int i=1; i<=n; i++){
		dp[i][0] = max(0ll, dp[i-1][0] + a[i]);
		dp[i][1] = max(0ll, max(dp[i-1][0], dp[i-1][1]) + (a[i] * x));
		dp[i][2] = max(0ll, max(dp[i-1][1], dp[i-1][2]) + a[i]);
		ans = max(ans, *max_element(dp[i], dp[i] + 3));
	}
	printf("%lld\n", ans);
}