C++14(g++5.4) 解法, 执行用时: 244ms, 内存消耗: 5104K, 提交时间: 2019-04-16 15:04:57

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf (ll)(1e13)
 
using namespace std;
 
typedef long long ll;
 
ll num[200005],f[200005];
int g[200005],pos[200005];
 
inline ll calc(ll p,int x,int y) {
  return p+num[y]*(y-x);
}
 
int dp(int n,ll v) {
  int l=1,r=1;
  pos[1]=0;g[0]=0;
  for(int j=1;j<=n;j++) {
    while (l<r&&calc(f[pos[l]],pos[l],j)>=calc(f[pos[l+1]],pos[l+1],j)) l++;
    f[j]=calc(f[pos[l]],pos[l],j)+v;
    g[j]=g[pos[l]]+1;
    while (l<r&&(f[j]-f[pos[r]])*(pos[r]-pos[r-1])<=(f[pos[r]]-f[pos[r-1]])*(j-pos[r])) r--;
    pos[++r]=j;
  }
  return g[n];
}
 
int main() {
  int n,k;
  scanf("%d%d",&n,&k);
  ll s=0,sum=0;
  for(int i=1;i<=n;i++) {
    int x,y;
    scanf("%d%d",&x,&y);
    s+=y;
    num[i]=x-s;
    sum+=num[i];
  }
  sort(num+1,num+n+1);
  ll l=-6LL*inf,r=6LL*inf;
  while (l<r) {
    ll m=(l+r)>>1;
    if (dp(n,m)<=k) r=m; else l=m+1;
  }
  dp(n,l);
  printf("%lld\n",f[n]-l*k-sum);
  return 0;
}
//我们发现这题和Cats Transport这题很像
//我们设a[i]=p[i]-Σd[i]
//我们按a[i]排序，发现每个农民带走的植物时a[i]连续的一段
//f[i][j]表示前j个农民,带走前i个植物的最小损失价值
//f[i][j]=min(f[i][j],f[i][j-1]+(i-k)*p[i]-(s[i]-s[k]))
//f[i][j]=f[i][j-1]+(i-k)*p[i]-(s[i]-s[k])
//斜率优化一波带走
//套上二分就A了 

C++11(clang++ 3.9) 解法, 执行用时: 381ms, 内存消耗: 10076K, 提交时间: 2019-12-30 19:17:31

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,mn,f[200010],g[200010],cnt[200010],q[200010],sum[200010],p[200010],d[200010];
double pd(ll x,ll y){
	return (double)(g[y]-g[x])/(double)(y-x);
}
ll solve(ll mid){
	ll i,l=1,r=1;
	q[1]=0;
	for(i=1;i<=n;i++){
		while(l<r&&pd(q[l],q[l+1])<=(double)p[i])l++;
		f[i]=g[q[l]]+i*p[i]-sum[i]-q[l]*p[i]+mid;
		cnt[i]=cnt[q[l]]+1;
		g[i]=f[i]+sum[i];
		while(l<r&&pd(i,q[r])<=pd(q[r-1],q[r]))r--;
		q[++r]=i;
	}
	return cnt[n];
}
int main(){
	ll i,l,r,mid;
	scanf("%lld%lld",&n,&k);
	for(i=1;i<=n;i++){
		scanf("%lld%lld",&p[i],&d[i]);
	}
	d[1]=0;
	for(i=2;i<=n;i++){
		d[i]+=d[i-1];
		p[i]=p[i]-d[i];
	}
	sort(p+1,p+n+1);
	for(i=1;i<=n;i++)sum[i]=sum[i-1]+p[i];
	l=0;r=1e14;mn=r;
	while(l<=r){
		mid=(l+r)/2;
		if(solve(mid)<=k)mn=mid,r=mid-1;
		 else l=mid+1;
	}
	solve(mn);
	printf("%lld",f[n]-cnt[n]*mn);
}