【NOIP 2018】摆渡车
2024-10-19 12:39:24
前情提要
是的 我终于回来补坑了
一年了哇 你这个鸽子王
斜率优化版本
今天在复习斜率优化的时候才想起来这个题
定义就不设了 大家想看可以看上面那个原版
怎么斜率优化呢?
我们考虑\(i\)点是当前的目标状态 \(j\)点是当前的最优决策
则有如下这个式子
\(f_i = i\ *\ (cnt_i - cnt_j)\ -\ (sum_i\ -\ sum_j)\ +\ f_j\)
拆
\(f_i = i\ *\ cnt_i\ -\ i\ *\ cnt_j\ -\ sum_i\ +\ sum_j\ +\ f_j\)
根据斜率优化的套路
把和\(j\)有关的放在左边 \(同时和i和j的项放在中间\) \(只和i有关的放在右边\)
\(f_j\ + sum_j\ =\ i\ *\ cnt_j\ +\ f_i\ - \ sum_i\ +\ i\ *\ cnt_i\)
\(f_j + sum_j\)是\(y\)
\(i\)是\(k\)
\(cnt_j\)是\(x\)
\(f_i\ - \ sum_i\ +\ i\ *\ cnt_i\)是\(b\)
接下来就是常规操作了 对于\(i\) 在队列中压入\(i - m\) 维护一个斜率的下凸包即可
代码
#include <cstdio>
#include <algorithm>
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, l = 1, r, cnt[maxT], sum[maxT], q[maxT], f[maxT];
inline double getSlope(int u, int v) { return (double) (f[v] + sum[v] - f[u] - sum[u]) / (cnt[u] == cnt[v] ? 1e-9 : cnt[v] - cnt[u]); }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &ti); t = std::max(t, ti);
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 >= 0) {
while (l < r && getSlope(q[r - 1], q[r]) >= getSlope(q[r], i - m)) { r--; }
q[++r] = i - m; // 把可能成为最优解的推入队列.
}
while (l < r && getSlope(q[l], q[l + 1]) <= i) { l++; } // 把不可能成为最优解的弹出队列.
f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
if (l <= r) { f[i] = std::min(f[i], f[q[l]] + (cnt[i] - cnt[q[l]]) * i - (sum[i] - sum[q[l]])); } // 斜率优化转移.
}
for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
printf("%d\n", ans);
return 0;
}
最新文章
- div中设置滚动条的问题
- Linux安装库文件(环境变量和makefile)
- VS2013全攻略
- 实现table的单线边框的办法
- lamp遇到问题
- 树莓派上Java程序作为linux服务并开机自动启动
- VaildForm 自定义提示消息
- [原创] 用两个stack实现queue的功能
- Spring动态配置多数据源
- bootstrap的弹出框
- SGU 385 Highlander(期望)
- poj 1088 动态规划+dfs(记忆化搜索)
- eclipse/myeclipse使用技巧
- Python Keras module &#39;keras.backend&#39; has no attribute &#39;image_data_format&#39;
- 爬虫学习--MOOC爬取豆瓣top250
- jquery----jquery中的属性的利用
- <;文档学习>;AirSim/using_car.md Choosing Your Vehicle: Car or Multirotor
- android: shell 命令
- Ubuntu 16.04 构建 Headless VNC 服务器
- vue 使用Slot 分发内容 学习总结。
热门文章
- fastjson反序列化-JdbcRowSetImpl利用链
- vue基础-组件&;插槽
- Egg.js学习与实战系列 &#183; Post请求`csrf token`问题
- Java版人脸检测详解下篇:编码
- linux系统上国际化失败
- STL模板
- inline hook原理和实现
- You (oracle) are not allowed to access to (crontab) because of pam configura
- Pod 健康检查和服务可用性检查
- Centos7上安装docker (新手版本)