题解:
是一道不错的题啦。。。
首先我们会发现一个人取得应该是一段 不然这题完全没法做
自然的想到将每个点要在至少什么时刻从初始位置出发算出
那么我们离散化后按照这个排序
答案=从初始开始掉生命-多掉的生命+从起点过去掉的生命(后面两项是定值)
然后我们发现就变成了一个dp
f[i][k]=f[j][k-1]+(i-j)*t[i]
这个东西比较显然是可以斜率优化的
然后这个是个凸函数也比较容易yy
所以就可以上wqs二分了
因为斜率单增所以复杂度nlogn
代码:
#include <bits/stdc++.h> using namespace std; #define ll long long #define rint register ll #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) const ll N=3e5; const double ee=1.00000000000000; const ll INF=1e18; ll h,t,g[N],f[N],s[N],n,m; struct re{ ll p,d,a,b; }a[N]; bool cmp(re x,re y) { return x.a<y.a; } bool pd(ll y1,ll x1,ll y2,ll x2,ll y3,ll x3) { return ee*(y3-y2)/(x3-x2)<=ee*(y2-y1)/(x2-x1); } bool check(ll k) { ll h=1,t=1; s[1]=0; rep(i,1,n) { while (h<t&&(f[s[h]]-s[h]*a[i].a >f[s[h+1]]-(s[h+1])*a[i].a ||((f[s[h]]-s[h]*a[i].a ==f[s[h+1]]-(s[h+1])*a[i].a&& g[s[h]]>g[s[h+1]])))) h++; f[i]=f[s[h]]+(i-s[h])*a[i].a+k; g[i]=g[s[h]]+1; while (h<t&&pd(f[s[t-1]],s[t-1],f[s[t]] ,s[t],f[i],i)) t--; s[++t]=i; } if (g[n]<=m) return(1); else return(0); } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m; ll ans=0; rep(i,1,n) { cin>>a[i].p>>a[i].d; a[i].d+=a[i-1].d; ans+=a[i].d; ans-=a[i].p; a[i].a=a[i].p-a[i].d; } sort(a+1,a+n+1,cmp); ll h=0,t=INF; while (h<t) { ll mid=(h+t)/2; if (check(mid)) t=mid; else h=mid+1; } check(h); cout<<ans+f[n]-m*h<<endl; return 0; }