简单dp
众所周知，没有修改的最大连续子段和是可以用dp[i]表示以i结尾的最大连续子段和，O(n)的方法求出来的。
我们试着把这样的转移方式代入本题。
那么就会发现其实我们考虑到a[i]的时候有三种情况。
我们在考虑a[i]的时候还没有去让某个区间乘以x
我们在考虑a[i]的时候正在让某个区间乘以x
我们在考虑a[i]的时候已经让某个区间乘以了x（区间已固定）
对应三个不同的情况，可以给dp数组再加一维，dp[1][i], dp[2][i], dp[3][i]分别表示上面三种状态。
那么转移方程很容易写出：
dp[1][i] = max(dp[1][i - 1] + a[i], 0)
dp[2][i] = max(dp[1][i - 1] + k * a[i], dp[2][i - 1] + k * a[i], 0)
dp[3][i] = max(dp[2][i - 1] + a[i], dp[3][i - 1] + a[i], 0)
我们在for循环dp的过程中不断更新答案即可。
#include#define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)using namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){ int X = 0, w = 0; char ch = 0; while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 300005;ll a[N], dp[4][N], ans;int n, x;int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> x; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++){ dp[1][i] = max(dp[1][i - 1] + a[i], 0LL); dp[2][i] = max(dp[2][i - 1] + a[i] * x, dp[1][i - 1] + a[i] * x, 0LL); dp[3][i] = max(dp[3][i - 1] + a[i], dp[2][i - 1] + a[i], 0LL); ans = max(ans, max(dp[1][i], dp[2][i], dp[3][i])); } cout << ans << endl; return 0;}