洛谷P4983 忘情 (WQS二分+斜率优化)

忘情水二分模板题，最优解对划分段数的导数满足单调性（原函数凸性）即可使用此方法。

详细题解洛谷里面就有，不啰嗦了。

二分的临界点让人有点头大。。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef double db;
 5 const ll N=5e5+10,inf=0x3f3f3f3f3f3f3f3f;
 6 ll n,m,hd,tl,a[N],S[N],dp[N],cnt[N];
 7 struct P {ll x,y,c;} q[N];
 8 P operator-(P a,P b) {return {a.x-b.x,a.y-b.y,a.c};}
 9 ll cross(P a,P b) {return a.x*b.y-a.y*b.x;}
10 ll solve(ll m) {
11     hd=tl=0;
12     q[tl++]= {0,0,0};
13     for(ll i=1; i<=n; ++i) {
14         for(; hd+1<tl&&cross((P) {1,2*(S[i]+1)},q[hd+1]-q[hd])<=0; ++hd);
15         dp[i]=q[hd].y-2*(S[i]+1)*q[hd].x+(S[i]+1)*(S[i]+1)+m;
16         cnt[i]=q[hd].c+1;
17         P np= {S[i],dp[i]+S[i]*S[i],cnt[i]};
18         for(; hd+1<tl&&cross(q[tl-1]-q[tl-2],np-q[tl-1])<=0; --tl);
19         q[tl++]=np;
20     }
21     return cnt[n];
22 }
23 ll bi(ll l,ll r) {
24     ll ret;
25     while(l<=r) {
26         ll mid=(l+r)>>1;
27         if(solve(mid)>=m)ret=dp[n]-m*mid,l=mid+1;
28         else r=mid-1;
29     }
30     return ret;
31 }
32 int main() {
33     scanf("%lld%lld",&n,&m);
34     for(ll i=1; i<=n; ++i)scanf("%lld",&a[i]);
35     for(ll i=1; i<=n; ++i)S[i]=S[i-1]+a[i];
36     printf("%lld
",bi(0,inf));
37     return 0;
38 }