CF-311B Cats Transport(斜率优化DP)
题目链接
题目描述
小S是农场主,他养了 \(M\)只猫,雇了 \(P\) 位饲养员。
农场中有一条笔直的路,路边有 \(N\) 座山,从 \(1\) 到 \(N\)编号。
第 \(i\) 座山与第 \(i-1\) 座山之间的距离为 \(D_i\)。
饲养员都住在 \(1\) 号山。
有一天,猫出去玩。
第 \(i\) 只猫去 \(H_i\)号山玩,玩到时刻 \(T_i\)
停止,然后在原地等饲养员来接。
饲养员们必须回收所有的猫。
每个饲养员沿着路从 $1 $号山走到 N 号山,把各座山上已经在等待的猫全部接走。
饲养员在路上行走需要时间,速度为\(1\)米/单位时间。
饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。
例如有两座相距为 1 的山,一只猫在 2 号山玩,玩到时刻 3 开始等待。
如果饲养员从 1 号山在时刻 2 或 3 出发,那么他可以接到猫,猫的等待时间为 0 或 1。
而如果他于时刻 1 出发,那么他将于时刻 2 经过 2 号山,不能接到当时仍在玩的猫。
你的任务是规划每个饲养员从 1 号山出发的时间,使得所有猫等待时间的总和尽量小。
饲养员出发的时间可以为负。
分析
接猫是任务,p个饲养员,每个饲养员接猫可以看作把几个猫放到一个集合。
第\(i\)个猫被一个饲养员从1号点出发去接,等待时间与饲养员出发时刻有关。但出发时刻必须大于\(T[i] -\sum_{1}^iD[i]\)。将这个时间排个序,可以把这个猫看作若干个任务,可以贪心的证明把这些排序后的任务分成若干个不相交的部分会是最优的,如果相交了会有多余的花费(脑部一下,中间空出来的几个分到别的组,这几个猫的等待时间白白增加)。
假设算出了前\(k-1\)个饲养员的所有解。\(d[k][i]\)表示前\(k\)个饲养员接走前 \(i\)只猫时的答案。转移方程呼之欲出
\]
把max去掉,得到最优的\(j\)满足
\]
标准斜率优化DP,\(A_i\)递增。
另外由于P最大200,所以可以滚动数组优化掉一维
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll H[N],D[N],A[N],s[N],d[2][N],n,m,p,T[N];
int q[N];
int main(){
scanf("%lld%lld%lld",&n,&m,&p);
for(int i=2;i<=n;i++){
scanf("%lld",&D[i]);
D[i] += D[i-1];
}
for(int i=1;i<=m;i++){
scanf("%lld%lld",&H[i],&T[i]);
A[i] = T[i] - D[H[i]];
}
sort(A+1,A+1+m);
for(int i=1;i<=m;i++){
s[i] = s[i-1] + A[i];
}
for(int i=1;i<=m;i++)d[1][i] = 1ll * i * A[i] - s[i];
for(int k=2,w=0;k<=p;k++,w^=1){
int l = 0,r = 0;
for(int i=1;i<=m;i++){
while(l < r && (d[w^1][q[l+1]] - d[w^1][q[l]] + s[q[l+1]] - s[q[l]]) <= A[i] * ((q[l+1] - q[l])))l++;
int j = q[l];
//cout << l << ' ' << r << ' ' << j << ' ' << d[w^1][j] << endl;
d[w][i] = d[w^1][j] + 1ll * (i-j) * A[i] - (s[i]-s[j]);
while(l < r && (d[w^1][q[r-1]] - d[w^1][q[r]] + s[q[r-1]] - s[q[r]]) * (q[r-1]-i) > (d[w^1][q[r-1]] - d[w^1][i] + s[q[r-1]] - s[i]) * (q[r-1] - q[r]))r--;
q[++r] = i;
}
}
printf("%lld\n",d[p&1][m]);
return 0;
}
最新文章
- angularjs中ng-change使用方法
- php综合应用
- Jquery局部刷新小案列
- Bootstrap系列 -- 32. 按钮垂直分组
- WPF 之 利用Visibility属性进行Item模板切换
- codeforces Gym 100500C D.Hall of Fame 排序
- Android开发之自定义圆角矩形图片ImageView的实现
- OpenCV 最小二乘拟合方法求取直线倾角
- python编程基础知识—列表(一)
- xamarin android 在代码中如何设置文本颜色
- 【Unity Shaders】Alpha Test和Alpha Blending
- BZOJ_3252_攻略_线段树+dfs序
- 【算法】Bert预训练源码阅读
- 查看Oracle中存储过程长时间被卡住的原因
- Oracle 10g RAC OCR、Voting disk更换
- EFI Windows 7 activition
- 补充:ajax post 方式请求
- rsync简介与rsync+inotify配置实时同步数据
- tensorflow学习之(一)预测一条直线y = 0.1x + 0.3
- Android WebView 文明踩坑之路
热门文章
- 新来的运维这样用HDFS,CIO都懵了&#183;&#183;&#183;
- ORA-39700: database must be opened with UPGRADE option【转】
- python的默认参数的一个坑
- 实现一个简单的 Linux Shell(C++)
- win10/windows 安装Pytorch
- alter column和modify column
- 视图V_160M和表T_160M的维护
- Java中的基本数据类型与引用数据类型
- 前端面试之HTTP状态码!
- 大数据系列4:Yarn以及MapReduce 2