[002] P11642题解（幸运草）

由于很难（根本不能？）确定某段区间往双向拓展后是否有对答案贡献更大的修改区间，还想不到可解的贪心。不过使用类 P1115 的新手级 dp 就能很轻松找到最好的修改区间来解决本题。

解析部分

首先构造

b_i=x-a_i

（即修改当前位置对答案的贡献），则要修改的区间

[l,r]

为

b

中最大子段时，即

\sum\limits_{i=l}^{r}{(x-a_i)}

最大。进一步地，因为答案的变化只与修改的区间有关，此时

\sum\limits_{i=1}^{n}{(x-a_i)}

也最大。

于是我们可以先找出

b

中最大的子段，本题可以考虑用简单的 dp。把

dp_i

定义为

[1,i]

中以

i

结尾的最大子段和。那么由于

i

位置既可以承接末尾于

i-1

位置的子段并对其延长，也可以另作一段的开头。得到转移方程：

dp_i=\max(dp_{i-1}+b_i,b_i)

然后在转移时，需要判断一下当前位置应该属于以上两者中哪一种情况，用变量

l,r

实时更新当前最大子段的首尾，此时的

l,r

同样也是

[1,i]

中对答案贡献最大的修改区间

[l,r]

，用前缀和维护实时求出如果修改该区间得到的答案（即原

a

中

[1,l-1]

，

[r+1,n]

再加上修改区间对答案的贡献：

x(r-l+1)

的和），对于所有可能的

i

答案求出最大值。以

O(n)

解决了本题。

代码部分

为了保全祖宗建议使用 long long 来实现本题。）

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,x,l,r,ans,a[100005],f[100005],b[100005],dp[100005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i],f[i]=f[i-1]+a[i],b[i]=x-a[i];
	ans=f[n];//需要注意不修改的特殊情况
	for(int i=1;i<=n;i++){
		if(dp[i-1]+b[i]>b[i]){
			r=i;//事实上在过程中 r 一定等于 i
		}
		else l=r=i;
		dp[i]=max(dp[i-1]+b[i],b[i]);
		ans=max(ans,(r-l+1)*x+f[l-1]+f[n]-f[r]);
	}
	cout<<ans;
	return 0;
}
/*

*/

[002] P11642题解（幸运草）

文章操作

解析部分

代码部分

相关推荐

评论

[002] P11642题解（幸运草）