[NOIP2018]摆渡车
2024-08-21 15:11:24
Description:
有 n 名同学要乘坐摆渡车从人大附中前往人民大学,第 i位同学在第 t 分钟去 等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费m分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。
凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?
Hint:
\(n,m<=500,t<=4*10^6\)
Solution:
比较好的一道线性dp
\[f[i+m+j]=\sum min(f[i]+s[i+m+j]-s[i]+b[i]*(m+j))
\]
\]
\((0 \le j<m)\)
其中:
\(s_i表示从1到i所有人等车时间的前缀和,b_i表示人数的前缀和\)
#include<bits/stdc++.h>
using namespace std;
const int mxn=5050,mxt=4e6+5;
int n,m,T,t=mxt,ans=mxt;
int a[mxn],b[mxt],f[mxt],s[mxt];
inline void checkmax(int &x,int y) {if(x<y) x=y;}
inline void checkmin(int &x,int y) {if(x>y) x=y;}
int main()
{
scanf("%d%d",&n,&m); memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i) {
scanf("%d",a+i); ++b[a[i]];
checkmin(t,a[i]),checkmax(T,a[i]);
}
sort(a+1,a+n+1); int cnt=1,tot=0;
for(int i=0;i<=T+2*m;++i) {
while(i>a[cnt]&&cnt<=n) ++tot,++cnt;
b[i]+=b[i-1];
s[i]=s[i-1]+tot;
}
f[0]=0;
for(int i=0;i<=T+2*m;++i) f[i]=s[i];
for(int i=0;i<=T+m;++i) {
checkmin(f[i+m],f[i]+(s[i+m]-s[i])-b[i]*m);
for(int j=1;j<m;++j)
if(b[i]!=b[i+m+j]) //剪枝,最多转移到i+m
checkmin(f[i+m+j],f[i]+(s[i+m+j]-s[i])-b[i]*(m+j));
}
for(int i=T;i<=T+m;++i) checkmin(ans,f[i]);
printf("%d",ans);
return 0;
}
最新文章
- execl表格VLOOKUP函数的使用
- codeforces 510B. Fox And Two Dots 解题报告
- ibatis中的$和#的区别
- SecureCrt脚本(二)二级对象之Dialog
- Qt编译安装后中文无法显示问题
- oracle 实例名和服务名以及数据库名区别
- android114 c转换成c++
- 【转】Android:控件Spinner实现下拉列表
- 一个类似抖音 APP 拍摄按钮效果的控件
- 【Idea】idea waiting until last debugger command completes
- 数据库性能测试:sysbench用法详解
- LeetCode算法题-Sum of Two Integers(Java实现)
- __dict__(字典的另一种用法)
- AS3.0:给图片添加滤镜模糊与斜角效果
- floor()函数 和round()函数的区别
- 设计模式之装饰模式(Decorator)摘录
- OllyDbg安装教程
- 洛谷P3557 GRA-Tower Defense Game [POI2013] 构造
- Workbook对象的方法总结(一)
- ehcache 缓存管理工具