bzoj 2726 任务安排 斜率优化DP
2024-09-01 07:30:31
这个题目中 斜率优化DP相当于存在一个 y = kx + z
然后给定 n 个对点 (x,y) 然后给你一个k, 要求你维护出这个z最小是多少。
那么对于给定的点来说 我们可以维护出一个下凸壳,因为如果存在一个上突壳的话,那么上突壳的点是一定不会被选上的。
所以对于解来说,只有下凸壳的点再会被选到。
所以我们就可以用单调队列维护处这个下凸壳。
假如我们保证给定的k是单调递增的, 那么我们就可以把前面一段不需要的东西给删掉。
假如k不是单调的,则我们就可以用二分找到第一个 > 询问k的答案。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 3e5 + ;
LL F[N], sumt[N], sumc[N];
int q[N];
int L = , R = ;
int solve(LL tmp){
if(L == R) return L;
int l = L, r = R - ;
while(l <= r){
int m = l+r >> ;
if(F[q[m+]] - F[q[m]] <= (tmp)*(sumc[q[m+]]-sumc[q[m]])) l = m+;
else r = m-;
}
return l;
}
int main(){
int n, s;
scanf("%d%d", &n, &s);
for(int i = ; i <= n; ++i){
scanf("%lld%lld", &sumt[i], &sumc[i]);
sumt[i] += sumt[i-];
sumc[i] += sumc[i-];
}
for(int i = ; i <= n; ++i){
int p = solve(s+sumt[i]);
F[i] = F[q[p]] - (s+sumt[i]) * sumc[q[p]] + sumt[i] * sumc[i] + s * sumc[n];
while(L < R && ((F[q[R]]-F[q[R-]])*(sumc[i]-sumc[q[R]]) >= (F[i]-F[q[R]])*(sumc[q[R]]-sumc[q[R-]]))) R--;
q[++R] = i;
}
cout << F[n] << endl;
return ;
}
最新文章
- Oracle监控用户索引使用情况,删除无用索引
- sqlServer数据库实现不同库之间表迁移
- Google开源库-Volley的使用
- 自定义Toast和RatingBar的简单用例
- js 百度地图
- ChIP-seq Peak caller MACS index out of range问题解决
- deep learning学习环境Theano安装(win8+win7)
- Executing a script from Nagios event handler fails to run
- Java中方法的重载
- Javascript字符串拼接小技巧
- Swift3.0服务端开发(二) 静态文件添加、路由配置以及表单提交
- 谈谈RDD、DataFrame、Dataset的区别和各自的优势
- 使用JAXP进行XM解析(基于DOM)
- 《Java从入门到放弃》入门篇:springMVC数据传递
- mvc4 实现自己的权限验证 仿Authorize与AllowAnonymous原理
- Elasticsearch笔记三之版本控制和插件
- rocketmq生产者代码分析
- js计算地球(地图)上两点的直线距离
- git学习小游戏
- java8学习笔记之lambda表达式