P11642 题解

· · 题解

萌新第一次写题解，不明之处见谅

【MX-J10】梦熊 J 组 · 猕猴桃赛 &「TAOI」Round 3（同步赛）T2 （P11642） 题解

考虑dp。

首先先设置状态 f_i ,表示到第 i 位的最大和，可这样并不好列出状态转移方程，因为题目中要求修改的区域为连续的子段，这样很有可能修改多个连续的子段，这不是我们能接受的。

因此我们需要再添一维，即 f_{i,j}。

而这么大的空间肯定不行，所以第二维只能是 0/1 ，或其他小数字，类似于结构体。

因为每到新的一位，只有可能有三种状态：要么未使用过区间变，要么正在使用区间变，要么已使用过区间变。于是我们可以设 f_{i,0} 的状态为到第 i 位，且已使用过区间变的最大和，f_{i,1} 的状态为到第 i 位，且正在使用区间变的最大和，f_{i,2} 的状态为到第 i 位，且未使用过区间变的最大和。

$f_{i,1}$ 只能由 $f_{i-1,1}$ 或 $f_{i-1,2}$ 转移来（要么维持以前的正在使用区间变的状态，要么由以前的未使用过区间变的状态转移来） $f_{i,2}$ 只能由 $f_{i-1,2}$ 转移来（这个就不用多说了吧） 其实 $f_{i,2}$ 本质上是前缀和。 这样的话，状态转移方程就很好写了： $$f_{i,0}=\max(f_{i-1,0},f_{i-1,1})+a_i$$ $$f_{i,1}=\max(f_{i-1,1},f_{i-1,2})+x$$ $$f_{i,2}=f_{i-1,2}+a_i$$ 最终将 $f_{n,0},f_{n,1},f_{n,2}$ 取个最大值就行了。不难。 ``` #include<bits/stdc++.h> #define ll long long using namespace std; ll n,x,a[100005],sum[100005],f[100005][3],maxn; int main() { cin>>n>>x; for(ll i=1;i<=n;i++) { cin>>a[i]; } for(ll i=1;i<=n;i++) { f[i][2]=f[i-1][2]+a[i]; f[i][1]=max(f[i-1][1],f[i-1][2])+x; f[i][0]=max(f[i-1][0],f[i-1][1])+a[i]; } cout<<max(max(f[n][0],f[n][1]),f[n][2]); } ```