丘中有麻plant
改自这儿，by ZBQ。
还有隐藏的一页不放了。。
直接走下去的话，如果开始时间确定那么到每个点的时间确定，把time减去dis就可以去掉路程的影响了。
这样对于减去d后的t，如果想要摘一部分，那么应是取其中最大的t恰好摘它，其它t较小的会早熟然后等着。。(意会一下吧)
所以t大的会对t小的产生贡献，而要恰好摘t小的，那就摘不了t大的了。
所以对t排序并不会影响答案。从小到大依次分K段就行了。i对其中每个作物j的贡献是ti-tj。
注意t相等时虽然会同时摘，但是不能直接去重！因为如果不恰好摘它们，其它的会对它们所有产生贡献。。
所以考试的时候只有10分。。
某些剪枝之类的优化还是想好再加吧。没啥用又不会被卡T，不如不加。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2e5+5;
int n,K,q[N],num[N];//longlong
LL tm[N],sum[N],f[N],C;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Spec
{
int n,Now,q[N];//longlong
LL sum[N],f[2][N];
inline LL Y(int j,int k){
return f[Now][j]-f[Now][k]+sum[j]-sum[k];
}
inline LL X(int j,int k){
return j-k;
}
inline LL Calc(int fr,int to,int k){
return f[Now][fr]+(to-fr)*tm[to]-sum[to]+sum[fr];
}
void Main()
{
for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+(LL)tm[i];
memset(f,0x7f,sizeof f);
f[0][0]=0, Now=0;
for(int j=1; j<=K; ++j, Now^=1)
{
int h=1,t=1; q[1]=j-1;// q[1]=0;
for(int i=j; i<=n; ++i)
{
while(h<t && Y(q[h+1],q[h])<=1ll*tm[i]*X(q[h+1],q[h])) ++h;
f[Now^1][i]=Calc(q[h],i,j);
while(h<t && Y(i,q[t])*X(q[t],q[t-1])<=Y(q[t],q[t-1])*X(i,q[t])) --t;
q[++t]=i;
}
}
printf("%I64d\n",f[Now][n]);
}
}
inline LL Y(int j,int k){
return f[j]-f[k]+sum[j]-sum[k];
}
inline LL X(int j,int k){
return j-k;
}
inline LL Calc(int fr,int to){
return f[fr]+tm[to]*(to-fr)-sum[to]+sum[fr]+C;
}
void Solve()
{
f[0]=num[0]=0;
int h=1,t=1; q[1]=0;
for(int i=1; i<=n; ++i)
{
while(h<t && Y(q[h+1],q[h])<=tm[i]*X(q[h+1],q[h])) ++h;
f[i]=Calc(q[h],i), num[i]=num[q[h]]+1;
while(h<t && Y(i,q[t])*X(q[t],q[t-1])<=Y(q[t],q[t-1])*X(i,q[t])) --t;
q[++t]=i;
}
}
int main()
{
freopen("plant.in","r",stdin);
freopen("plant.out","w",stdout);
n=read(), K=read();
int s=0;
tm[1]=read(), read();
for(int i=2; i<=n; ++i) tm[i]=read()-(s+=read());
std::sort(tm+1,tm+1+n);
// int cnt=n; n=1;// WA!
// for(int i=2; i<=cnt; ++i) if(tm[i]!=tm[i-1]) tm[++n]=tm[i];
for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+tm[i];
if(1ll*n*K<=2e7) {Spec::n=n, Spec::Main(); return 0;}
// Spec::n=n, Spec::Main(); return 0;
LL l=sum[n]*n, r=-l;
if(l>r) std::swap(l,r);
while(l<=r){
if(C=l+r>>1, Solve(), num[n]>K) l=C+1;
else r=C-1;
}
C=l, Solve();
// C=r+1, Solve();
printf("%I64d\n",f[n]-C*K);
return 0;
}
这是\(O(n^2k)\)暴力和\(O(nk)\)斜率优化，还有个改double的带权二分(开始拍出错tm[]爆int了)，都去重了所以对拍虽然过了然而。。
就这题会所以特别不嫌麻烦。
暴力：
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
//#define int long long
typedef long long LL;
const int N=1e4+5;
int n,K,tm[N];
LL sum[N],f[N][250];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline LL Calc(int fr,int to,int k){
return f[fr][k-1]+1ll*(to-fr)*tm[to]-sum[to]+sum[fr];
}
int main()
{
freopen("plant.in","r",stdin);
// freopen("plant.out","w",stdout);
freopen("violence.out","w",stdout);
n=read(), K=read();
int s=0;
tm[1]=read(), read();
for(int i=2; i<=n; ++i) tm[i]=read()-(s+=read());
// for(int i=1; i<=n; ++i) printf("%d:%d\n",i,tm[i]);
std::sort(tm+1,tm+1+n);
int cnt=n; n=1;
for(int i=2; i<=cnt; ++i) if(tm[i]!=tm[i-1]) tm[++n]=tm[i];
// for(int i=1; i<=n; ++i) printf("%d:%d\n",i,tm[i]);putchar('\n');
for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+(LL)tm[i];
memset(f,0x7f,sizeof f);
f[0][0]=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=K; ++j)
for(int k=0; k<i; ++k)
f[i][j]=std::min(f[i][j],Calc(k,i,j));
printf("%I64d\n",f[n][K]);
return 0;
}
裸斜率优化
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=2e5+5;
int n,K,Now,q[N];//longlong
LL tm[N],sum[N],f[2][N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline LL Y(int j,int k){
return f[Now][j]-f[Now][k]+sum[j]-sum[k];
}
inline LL X(int j,int k){
return j-k;
}
inline LL Calc(int fr,int to,int k){
return f[Now][fr]+tm[to]*(to-fr)-sum[to]+sum[fr];
}
int main()
{
freopen("plant.in","r",stdin);
// freopen("plant.out","w",stdout);
freopen("slope.out","w",stdout);
n=read(), K=read();
int s=0;
tm[1]=read(), read();
for(int i=2; i<=n; ++i) tm[i]=read()-(s+=read());
std::sort(tm+1,tm+1+n);
int cnt=n; n=1;
for(int i=2; i<=cnt; ++i) if(tm[i]!=tm[i-1]) tm[++n]=tm[i];
for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+tm[i];
memset(f,0x7f,sizeof f);
f[0][0]=0, Now=0;
for(int j=1; j<=K; ++j, Now^=1)
{
int h=1,t=1; q[1]=j-1;// q[1]=0;
for(int i=j; i<=n; ++i)
{
while(h<t && Y(q[h+1],q[h])<=tm[i]*X(q[h+1],q[h])) ++h;
f[Now^1][i]=Calc(q[h],i,j);
while(h<t && Y(i,q[t])*X(q[t],q[t-1])<=Y(q[t],q[t-1])*X(i,q[t])) --t;
q[++t]=i;
}
}
printf("%I64d\n",f[Now][n]);
return 0;
}
double带权二分。。：
//also right.
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define eps (1e-2)
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2e5+5;
int n,K,tm[N],q[N],num[N];//longlong
LL sum[N];
double f[N],C;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline double Y(int j,int k){
return f[j]-f[k]+sum[j]-sum[k];
}
inline double X(int j,int k){
return j-k;
}
inline double Calc(int fr,int to){
return f[fr]+1.0*(to-fr)*tm[to]-(double)sum[to]+(double)sum[fr]+C;
}
void Solve()
{
f[0]=num[0]=0;
int h=1,t=1; q[1]=0;
for(int i=1; i<=n; ++i)
{
while(h<t && Y(q[h+1],q[h])<=1.0*tm[i]*X(q[h+1],q[h])) ++h;
f[i]=Calc(q[h],i), num[i]=num[q[h]]+1;
while(h<t && Y(i,q[t])*X(q[t],q[t-1])<=Y(q[t],q[t-1])*X(i,q[t])) --t;
q[++t]=i;
}
}
int main()
{
freopen("plant.in","r",stdin);
// freopen("tmp.out","w",stdout);
n=read(), K=read();
int s=0;
tm[1]=read(), read();
for(int i=2; i<=n; ++i) tm[i]=read()-(s+=read());
std::sort(tm+1,tm+1+n);
int cnt=n; n=1;
for(int i=2; i<=cnt; ++i) if(tm[i]!=tm[i-1]) tm[++n]=tm[i];
for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+(LL)tm[i];
double l=1.0*sum[n]*n, r=-l;
if(l>r) std::swap(l,r);
while(r>l+eps){
if(C=(l+r)*0.5, Solve(), num[n]>K) l=C+1;
else r=C-1;
}
C=l, Solve();
// C=r+1, Solve();
printf("%I64d\n",(LL)(f[n]-C*K+0.5));
return 0;
}