题目分析
说实话，第一眼这题以为是贪心...（事实上我看所有动态规划都像贪心）。
然后接着发现贪心明显做不了，又看见最大子段和，很容易联想到 \(\text{dp}\)。
在设计状态的时候，我们考虑有哪些状态影响结果：
-
当前处于序列的哪一位
-
是否使用了魔法
开始以为只用设计用和不用两种状态，结果后来发现实际上有三种状态：
- 不用魔法
记状态为 \(dp_{i,0}\)，直接从上一个状态转移过来即可。
\[dp_{i,0} = \max(dp_{i-1,0} + a_i,0) \]- 正在用魔法
先从 \(dp_{i,0}\) 转移过来，然后再与使用魔法后的结果比较。
\[dp_{i,1} = \max(dp_{i,0},dp_{i-1,1} + a_i \times x) \]- 已经使用完魔法
还是从 \(dp_{i,1}\) 转移过来，然后另一边从 \(dp_{i-1,2}\) 转移过来，加上题中所给的 \(a_i\)。
\[dp_{i,2} = \max(dp_{i,1},dp_{i-1,2} + a_i) \]最后 \(ans\) 直接求三者最大值即可。
贴上代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
int n,x;
int ans;
int a[maxn],dp[maxn][4];
inline void init(){
cin>>n>>x;
for(register int i=1;i<=n;++i) cin>>a[i];
}
signed main(){
init();
for(register int i=1;i<=n;++i){
dp[i][0]=max(dp[i-1][0]+a[i],0LL);
dp[i][1]=max(dp[i][0],dp[i-1][1]+a[i]*x);
dp[i][2]=max(dp[i][1],dp[i-1][2]+a[i]);
ans=max(ans,dp[i][2]);
}
cout<<ans;
}