P11642 题解
Bob1108
·
·
个人记录
提供一个有点诡异的动态规划思路。 \
在考场上看到的这题，感觉应该是贪心，发现好像不对啊，改了个动规思路。 \
俗话说得好，要想动规，必先设计状态。由于选择的区间是连续的，我们不妨设二维状态 dp_{i,0/1}。 \
$dp_{i,1}$ 表示前 $i$ 个数字中，选取第 $i$ 个的总和。显而易见，我们得到状态转移方程：$$dp_{i,1} \gets \max(dp_{i-1,1}+x,sum_{i-1}+x)$$。其中，$sum$ 表示前缀和数组。 \
来解释一下第二个方程，我们分两种情况来看。第一种，我们直接接上第 $i-1$ 个（这个就是 $dp_{i-1,1}+x$）。当然，我们也可以“自立门户”，前面的都不要，从第 $i$ 个开始更改，所以就是 $sum_{i-1}+x$。 \
最后提醒一句，一定要想着开 long long！ \
说了这么多，来看看代码吧。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e5 + 10;
int n, dp[M][2], a[M], x, sum[M];
signed main() {
cin >> n >> x;
for (int i = 1; i <= n; i ++)
cin >> a[i], sum[i] = sum[i - 1] + a[i];
dp[1][0] = a[1], dp[1][1] = x;
for (int i = 2; i <= n; i ++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i];
dp[i][1] = max(dp[i - 1][1] + x, sum[i - 1] + x);
}
cout << max(dp[n][1], dp[n][0]) << "\n";
return 0;
}
```