洛谷Cats Transport

题意翻译

Zxr960115 是一个大农场主。

他养了 $D_iDi 米。铲屎官们住在 11 号山丘。$

一天，猫子们外出玩耍。猫子 $H_iHi 游玩，在 T_iTi 时间结束他的游玩，然后在山丘 H_iHi 傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官直接从 H_1H1 走到 H_nHn，中间不停下，可以认为不花费时间的把游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间，并且足够强壮来带上任意数量的猫子。$

举个栗子，假装我们有两个山丘( $D_2=1D2=1 )，有一只猫子，他想去山丘 22 玩到时间 33。然后铲屎官如果在时间 22 或者时间 33 从 11 号山丘出发，他就能抱走猫子。如果他在时间 11 出发那么就不行(猫子还在玩耍)。如果铲屎官在时间 22 出发，猫子就不用等他（Delta T=0ΔT=0）。如果他在时间 33 出发，猫子就要等他 11 个单位时间。$

你的任务是安排每个铲屎官出发的时间，最小化猫子们等待的时间之和。

对于全部的数据，满足 $nle10^52≤n≤105，1le mle10^51≤m≤105，1le ple1001≤p≤100，1le D_i<10^41≤Di<104，1le H_ile n1≤Hi≤n，0le tle10^90≤t≤109。$

输入输出样例

输入 #1

输出 #1

3

_________________________________________________________

每一只猫，最初可以接到的时间减去路程时间，就是管理员最早出发可以接到这只猫的时间。
那么这样处理以后，就得到了接到每一只猫的最初时间。
这样题目就变成了把m只猫分给p个管理员，让他们去接就是了。
这样，首先将所有的猫的接他们的最初出发时间按大小排序。然后对这些猫进行分组并DP就可以了。
f[i][j]=min(f[x][j-1]+t[i]*i-t[i]*x-smt[i]+smt[x])
f[i][j]:前i只猫由j个人来借走
由于出现t[i]*x，所以考虑斜率优化！

在一本通评测网站，只能过部分，读入优化也用了，斜率也由出发给为了乘法。还是过不了。
洛谷过了！

_________________________________________________________

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int  maxn=1e5+10;
 5 ll dis[maxn],t[maxn],smt[maxn];
 6 ll n,m,p;
 7 ll f[maxn][105];
 8 ll q[maxn],l,r;
 9 inline ll y(ll a,ll j)
10 {
11     return f[a][j-1]+smt[a];
12 }
13 void readint(ll &x)
14 {
15     char c=getchar();
16     ll f=1;
17     for(;c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
18     x=0;
19     for(;c<='9'&& c>='0';c=getchar())x=x*10+c-'0';
20     x*=f;
21 }
22 int main()
23 {
24     readint(n);readint(m);readint(p);
25 //    scanf("%lld%lld%lld",&n,&m,&p);
26     for(ll i=2;i<=n;++i)
27     {
28 //        scanf("%lld",dis+i);
29         readint(dis[i]);
30         dis[i]+=dis[i-1];
31     }
32     for(ll hh,tt,i=1;i<=m;++i)
33     {
34 //        scanf("%lld%lld",&hh,&tt);
35         readint(hh);readint(tt);
36         t[i]=(ll)tt-dis[hh];
37     }
38     sort(t+1,t+1+m);
39     for(ll i=1;i<=m;++i)
40         smt[i]=t[i]+smt[i-1];
41     memset(f,0x3f,sizeof f);
42     f[0][0]=0;
43     for(ll j=1;j<=p;++j)
44     {
45         l=r=0;
46         for(ll i=1;i<=m;++i)
47         {
48             while(l<r && (y(q[l+1],j)-y(q[l],j))<=t[i]*(q[l+1]-q[l]))++l;
49             //getxl(q[l],q[l+1],j)<=t[i]
50             f[i][j]=f[q[l]][j-1]+t[i]*i-t[i]*q[l]-smt[i]+smt[q[l]];
51             while(l<r && (y(q[r],j)-y(q[r-1],j))*(i-q[r])>=(y(i,j)-y(q[r],j))*(q[r]-q[r-1]))--r;
52             //getxl(q[r-1],q[r],j)>=getxl(q[r],i,j)
53             q[++r]=i;
54         }
55     }
56     printf("%lld",f[m][p]);
57     return 0;
58 }

View Code