二分上界有多大开多大 二分上界有多大开多大 二分上界有多大开多大 重要的事情说三遍
又被bright神仙带着做题了
先无脑上wqs二分
我们可以把这个柿子画一下，区间的花费就变成(（sigema(l~r)i s[i]）+1)^2了
那么这个东西经过我艰苦的画柿子证明是满足四边形不等式的
然后就和贞鱼那题一样搞了？然后我就被卡常了qwq囧
其实是自己思维僵化得厉害
上个斜率优化不好吗2333333
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; int n;LL s[110000],f[110000],g[110000]; int h,t,q[110000]; LL Y(int j){return f[j]+s[j]*s[j]-2*s[j];} LL X(int j){return s[j];} void check(LL C) { h=1,t=0;q[++t]=0;f[0]=g[0]=0; for(int i=1;i<=n;i++) { while(h<t&&(Y(q[h+1])-Y(q[h]))<=(X(q[h+1])-X(q[h]))*2*s[i])h++; f[i]=f[q[h]]+(s[i]-s[q[h]]+1)*(s[i]-s[q[h]]+1)+C; g[i]=g[q[h]]+1; while(h<t&& (Y(q[t])-Y(q[t-1]))*(X(i)-X(q[t])) >= (Y(i)-Y(q[t]))*(X(q[t])-X(q[t-1])) )t--; q[++t]=i; } } int main() { int K; scanf("%d%d",&n,&K);s[0]=0; for(int i=1;i<=n;i++) scanf("%lld",&s[i]), s[i]+=s[i-1]; LL l=0,r=1e18,ans; while(l<=r) { LL mid=(l+r)/2; check(mid); if(g[n]>=K) { ans=f[n]-K*mid; l=mid+1; } else r=mid-1; } printf("%lld\n",ans); return 0; }
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; int n; LL s[110000],f[110000],g[110000]; LL val(int l,int r){return (s[r]-s[l]+1)*(s[r]-s[l]+1);} LL cost(int j,int i){return f[j]+val(j,i);}//由j这个决策点更新i的花费 struct node { int l,r,id; node(){} node(int L,int R,int ID){l=L;r=R;id=ID;} }q[110000]; void check(LL C) { int h=1,t=0;q[++t]=node(0,n,0); for(int i=1;i<=n;i++) { if(q[h].r<i)h++; q[h].l=i; f[i]=cost(q[h].id,i)+C; g[i]=g[q[h].id]+1; if(h>t||cost(i,n)<=cost(q[h].id,n)) { while(h<=t&&cost(i,q[t].l)<=cost(q[t].id,q[t].l))t--; if(h>t)q[++t]=node(i,n,i); else { int l=q[t].l,r=q[t].r,ans; while(l<=r) { int mid=(l+r)/2; if(cost(i,mid)>cost(q[t].id,mid)) { ans=mid; l=mid+1; } else r=mid-1; } q[t].r=ans; q[++t]=node(ans+1,n,i); } } } } int main() { int K; scanf("%d%d",&n,&K);s[0]=0; for(int i=1;i<=n;i++) scanf("%lld",&s[i]), s[i]+=s[i-1]; LL l=0,r=1e18,ans; while(l<=r) { LL mid=(l+r)/2; check(mid); if(g[n]>=K) { ans=f[n]-K*mid; l=mid+1; } else r=mid-1; } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/AKCqhzdy/p/9898577.html
