[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 来实现本题。）

#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;
}
/*

*/