0%

Project5017_摆渡车工作报告

摘要:斜率优化dp

P5017 摆渡车

题面

题目分析

先假设在$T_1 , T_2 , T_3 … T_k$时刻发车$(T_{i-1} +m \leq T_{i})$,那么得到总代价的式子:

$\sum_{i=1}^{k} \sum_{T_i-1 < t_j \leq T_i}(T_i - t_j)$

然后像分块一样化简这个和式(s为i秒前来到站台的人数):

$(\sum_{i=1}^{k}((s[T_i]-s[T_{i-1}])*T_i)-\sum_{i=1}^{n}t_i$

可以这样用整体法理解:把每次车来回的时间中等待的总人数求出来,乘上这个车下次到来的时刻,减去每个这段时间内等待的人来的时刻,就得到了这段时间的代价.

发现后面的和式是固定的,考虑使用dp求出前面和式的最小值.

设$f_i$表示i时刻发车的最小代价,不难得到以下转移方程:

$f_i = min \{ f_j + (s_i - s_j) * i \} \qquad (j \leq i -m或j = 0)$

得到答案减去$\sum_{i=1}^{n}t_i$即可.

然后这个转移显然可以斜率优化,设用k转移i比用j转移i优秀,得到如下式子:

$f_k + (s_i - s_k)i < f_j + (s_i - s_j)i$

移项,得:

$\frac{f_k - f_j}{s_k - s_j}<i$

维护一个上凸壳即可.

还有就是比较斜率时最好移项成乘法,不然精度太恶心了…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "cstdlib"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=4000010;
lxl n,m,tot,max,l,r,ans=INF;
lxl f[maxn],t[510],sum[maxn],q[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline double slope(lxl a,lxl b)
{
lxl ya=f[a],yb=f[b];
lxl xa=sum[a],xb=sum[b];
return (double)(yb-ya)/(double)(xb-xa);
}
int main(void)
{
n=read(),m=read();
for(R int i(1);i<=n;++i)t[i]=read(),sum[++t[i]]++,tot+=t[i],max=std::max(max,t[i]);
for(R int i(1);i<=m+max;++i)sum[i]+=sum[i-1];
for(R int i(1);i<=m+max;++i)
{
if(i>m)
{
lxl tmp=i-m;
// while(l<r&&slope(q[r-1],q[r])>=slope(q[r],tmp))--r;
while(l<r&&(f[q[r]]-f[q[r-1]])*(sum[tmp]-sum[q[r]])>=(f[tmp]-f[q[r]])*(sum[q[r]]-sum[q[r-1]]))--r;
q[++r]=tmp;
}
// while(l<r&&f[q[l]]-i*sum[q[l]]>=f[q[l+1]]-i*sum[q[l+1]])++l;
while(l<r&&f[q[l+1]]+sum[q[l]]*i<=i*sum[q[l+1]]+f[q[l]])++l;
f[i]=f[q[l]]+(sum[i]-sum[q[l]])*i;
if(i>=max)ans=std::min(ans,f[i]);
}
printf("%lld\n",ans-tot);
return 0;
}