摆渡车
定义，无比重要
显然的，我们有一个dp的想法，类似于递降子序列的想法
我们显然的，这是一个一维dp,所以，我们定义(f[i])函数，为(0)(-i)的时间内，所出现顾客的等待时间的最小值
但是，有问题，这样的状态，没有dp转移方程。。。。。因为，状态描述不清，你有一个发车间隔为(m)
所以我们吧(dp)的状态强化，为(dp[i])，表示在(i)时刻发车(0-i)时出现的乘客等待时间的的最小值
这样我们就把(dp)的状态描述清楚了我们再来推(dp)的转移方程
我们照着这个直接抄就好了
需要注意的是，我们在这里要做一个前缀和，让转移的复杂度降下来，但那也是(O(n^2))的会超时
不妨，我们即令(cnt_i)，(0-i)中出现的人数，而(sum_i)，为其出现时间(t_k)之和
(50pts)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
const int MaxT=4000011;
int n,m,ti,t,ans=0x7fffffff,cnt[MaxT],sum[MaxT],f[MaxT];
int main() {
n=read();
m=read();
for(int i=1;i<=n;i++){
ti=read();
t=max(ti,t);
cnt[ti]++;
sum[ti]+=ti;
}
for(int i=1;i<t+m;i++){
cnt[i]+=cnt[i-1];
sum[i]+=sum[i-1];
}
for(int i=0;i<t+m;i++){
f[i]=cnt[i]*i-sum[i];
for(int j=0;j<=i-m;j++){
f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
}
}
for(int i=t;i<t+m;i++){
ans=min(ans,f[i]);
}
printf("%d",ans);
return 0;
}
这能得到50ps的高分
(70pts)
我们再来想想优化，事实上我们枚举j时不需令(j)从0开始，我们减去无用的转移从
事实上，从贪心的角度出发，在这一段(>2m)的长度里，发一次车，一定比不发车要好，所以
我们令(i-2m<jle i-m)
这样根据写法，可以获得(70)至(75),分数
时间复杂度为(O(tm))
(100pts)
我们其实稍微看看，联想一下过河那个题，考虑到路径压缩，因为让人很稀疏，(t)很大，事实上无论如果你是循环枚举决策，只能是(O(tm));
然而在这个题里，考虑路径压缩的一个思想，但是那个题模1000,真的是无语了，解法不漂亮，在这个题里，数组是够的，然而你不能模一个东西，因为与(m)有关
在([i,i+m)),里如果没有让人，那我们把这一段往右移令，(f_i)=(f_{i-m}),j时间复杂度为(O(n^2m+t))
至于为什么有右移，我们的(dp)，定义为在第(i)时间发车的等待时间最小值，而([i,i+m))已经没有人了，在做(i+m)时上一辆的回来时间至近为(i),若不是
我们先证明一个引理：
- 任何顾客的等待时间不超过m(小于)
由此
得出我们剪枝的正确性。。。。
其实我也不确定。。但是对了？
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
const int MaxT=4000011;
int n,m,ti,t,ans=0x7fffffff,cnt[MaxT],sum[MaxT],f[MaxT];
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x;
}
int main() {
// freopen("1.in","r",stdin);
n=read();
m=read();
for(int i=1;i<=n;i++){
ti=read();
t=max(ti,t);
cnt[ti]++;
sum[ti]+=ti;
}
for(int i=1;i<t+m;i++){
cnt[i]+=cnt[i-1];
sum[i]+=sum[i-1];
}
for(int i=0;i<t+m;i++){
if(i>=m&&cnt[i-m]==cnt[i]){
f[i]=f[i-m];
continue;
}
f[i]=cnt[i]*i-sum[i];
for(int j=max(i-2*m+1,0);j<=i-m;j++){
f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
}
}
for(int i=t;i<t+m;i++){
ans=min(ans,f[i]);
}
printf("%d",ans);
return 0;
}
但是，我们知道，这样子一点也没有(bg),对吧，要优美、
考虑，之前做过的玩具装箱,不是一样的吗？
所以我们考虑斜率优化，，，
接下来是数学的操作
手稿
下面时正文推导
首先，为了书写方便令(j)为最优决策点
我们把dp方程做变形有
于是等号左边为(y)，(i)为(k),(cnt_j)为(x),(({f_i+sum_i-cnt_i*i} ))为(b),我们要求(b)
配个小图
不妨建立一个平面直角坐标系令每个点坐标为((cnt_i,f_j+sum_j))，这就很明显了，过这个点做一条斜率为(i)的直线，求截距最小值，再两个点斜率小于i时队首++,然后i点入队(提前要把一些不是凸包的点初队)
我们通过维护一个双端队列，来完成这个操作。
程序写的时候注意细节
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
const int MaxT=4000011;
int n,m,ti,t,ans=0x7fffffff,tail,head,cnt[MaxT],sum[MaxT],f[MaxT],que[MaxT];
double slope(int i,int j){
if(cnt[i]==cnt[j]) return double(f[j]+sum[j]-f[i]-sum[i])/1e-9;
else return double(f[j]+sum[j]-f[i]-sum[i])/double(cnt[j]-cnt[i]);
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x;
}
int main() {
// freopen("1.in","r",stdin);
n=read();
m=read();
for(int i=1;i<=n;i++){
ti=read();
t=max(ti,t);
cnt[ti]++;
sum[ti]+=ti;
}
for(int i=1;i<t+m;i++){
cnt[i]+=cnt[i-1];
sum[i]+=sum[i-1];
}
/*
for(int i=0;i<t+m;i++){
if(i>=m&&cnt[i-m]==cnt[i]){
f[i]=f[i-m];
continue;
}
f[i]=cnt[i]*i-sum[i];
for(int j=max(i-2*m,0);j<=i-m;j++){
f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
}
}
*/
head=1;tail=0;
for(int i=0;i<t+m;i++){
if(i<m){
f[i]=cnt[i]*i-sum[i];
continue;
}
while(head<tail&&slope(que[tail-1],que[tail])>=slope(que[tail-1],i-m))
tail--;
tail++;
que[tail]=i-m;
while(head<tail&&slope(que[head],que[head+1])<=i) head++;
f[i]=f[que[head]]+(cnt[i]-cnt[que[head]])*i-(sum[i]-sum[que[head]]);
}/*
for(int i=0;i<t+m;i++){
printf("%d %d
",i,f[i]);
}*/
for(int i=t;i<t+m;i++){
ans=min(ans,f[i]);
}
printf("%d",ans);
return 0;
}
时间复杂度(O(t)),我觉得很优秀了，不是吗。