【LG5017】[NOIP2018pj]摆渡车
2024-09-25 05:50:14
【LG5017】[NOIP2018pj]摆渡车
题面
题解
震惊!普及组竟然考斜率优化???
当然有其他的方法
首先我们转化一下模型
此题可以变为:
在一根时间轴上有一些点,每个时间点\(i\)有一个权值\(c_i\)(即在\(i\)开始等待人数,没有则为\(0\))
要求选一些时间点,每个时间点间隔不小于\(m\)
使得每个点的权值乘上它与第一个大于等于它时间的已选择的时间点到它的距离之和最小 感觉讲得好复杂
设\(dp[i]\)表示当我们强制选时间点\(i\)的最小值
则有转移方程\(dp[i]=\min{dp[j]+\sum_{k=j+1}^i{(i-k)*c_k}}\) \((\)\(0\)\(\leq\)\(j\)\(\leq\)\(i-m\)\()\)
次数直接转移的复杂度为\(O(n^3)\)
考虑怎么优化,设
\(sum1[i]=\sum_{j=0}^i{c_j}\)
\(sum2[i]=\sum_{j=0}^i{c_j*j}\)
然后方程化为\(dp[i]=\min dp[j]+i*sum1[i]-i*sum1[j]-sum2[i]+sum2[j]\) \((\)\(0\)\(\leq\)\(j\)\(\leq\)\(i-m\)\()\)
此时复杂度为\(O(n^2)\)
继续优化,此时用上斜率优化
去掉\(min\),则
\(dp[i]=dp[j]+i*sum1[i]-i*sum1[j]-sum2[i]+sum2[j]\)
移项得\(dp[j]+sum2[j]=i*sum1[j]+dp[i]-i*sum1[j]+sum2[i]\)
将\(dp[j]+sum2[j]\)视为\(y\)
将\(i\)视为\(k\)
将\(sum1[j]\)视为\(x\)
队列优化下凸壳即可
复杂度\(O(n)\)
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
#define MAX_T 4100000
int N, M, c[MAX_T];
int maxt, sum1[MAX_T], sum2[MAX_T];
int dp[MAX_T], q[MAX_T];
#define y(i) (dp[i] + sum2[i])
#define k(i) (i)
#define x(i) (sum1[i])
int main() {
cin >> N >> M;
for (int t, i = 1; i <= N; i++) cin >> t, c[t]++, maxt = max(maxt, t);
sum1[0] = c[0], sum2[0] = 0;
for (int i = 1; i < maxt + M; i++) {
sum1[i] = sum1[i - 1] + c[i];
sum2[i] = sum2[i - 1] + i * c[i];
}
int ans = INT_MAX;
int l = 1, r = 0;
for (int i = 0; i < maxt + M; i++) {
if (i - M >= 0) {
while (l < r && 1ll * (y(q[r]) - y(q[r - 1])) * (x(i - M) - x(q[r])) >=
1ll * (y(i - M) - y(q[r])) * (x(q[r]) - x(q[r - 1]))) -- r;
q[++r] = i - M;
}
while (l < r && 1ll * (y(q[l + 1]) - y(q[l])) <=
1ll * k(i) * (x(q[l + 1]) - x(q[l]))) ++l;
dp[i] = i * sum1[i] - sum2[i];
int j = q[l]; if (l <= r) dp[i] = min(dp[i], dp[j] + i * sum1[i] - i * sum1[j] - sum2[i] + sum2[j]);
}
for (int i = maxt; i < maxt + M; i++) ans = min(ans, dp[i]);
cout << ans << endl;
return 0;
}
最新文章
- iOS - 捕获应用程序崩溃日志
- 2016.10.29 NOIP模拟赛 PM 考试整理
- php-fpm中启用慢日志配置(用于检测执行较慢的PHP脚本)
- IE11错误:Exception in window.onload: An error has occuredJSPlugin.3005 解决方案
- angular.bind() 函数
- R中,去掉dataframe中的NA行
- 20135202闫佳歆--week 8 进程的切换和系统的一般执行过程--学习笔记
- Mysql-提示java.sql.SQLException: Cannot convert value &#39;0000-00-00 00:00:00&#39; from column 7 to TIMESTAMP.
- main函数中argc理解
- C语言redirection
- EDE,DEDE网站搬家,DEDECMS搬家教程,一看就会
- iOS zipzap读取压缩文件
- cocos2d-x 贝塞尔曲线的简单运用(CCBezierTo,CCBezierBy)
- 如何利用多核CPU来加速你的Linux命令 — awk, sed, bzip2, grep, wc等(转)
- webpack2系列step1
- 发送邮件,出现异常:服务器响应为: Error: need EHLO and AUTH first !";
- Idea导包与打包
- Spring官方文档下载
- C语言窗口例子
- SpringMVC 与 REST.