任务安排1
#include<bits/stdc++.h>
#define int long long
using namespace std; const int N=;
int n,s,t[N],c[N],f[N];
int sumt[N],sumc[N]; signed main(){
scanf("%lld%lld",&n,&s);
for(int i=;i<=n;i++) scanf("%lld%lld",&t[i],&c[i]),sumt[i]=sumt[i-]+t[i],sumc[i]=sumc[i-]+c[i];
memset(f,,sizeof f);
f[]=;
for(int i=;i<=n;i++){
for(int j=;j<i;j++)
f[i]=min(f[i],f[j]+(sumc[i]-sumc[j])*sumt[i]+s*(sumc[n]-sumc[j]));
//利用刷表法,将影响向后累加
}
printf("%lld\n",f[n]);return ;
}
任务安排2 数据规模变大
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; const int N=; long long f[N],sumt[N],sumc[N];
int q[N],n,s; int main(){
scanf("%d%d",&n,&s);
for(int i=;i<=n;i++){
int t,c;
scanf("%d%d",&t,&c);
sumt[i]=sumt[i-]+t;
sumc[i]=sumc[i-]+c;
}
memset(f,0x3f,sizeof f);
f[]=;
int head=,tail=;
q[]=;
for(int i=;i<=n;i++){
while(head<tail&&f[q[head+]]-f[q[head]]<=(s+sumt[i])*(sumc[q[head+]]-sumc[q[head]])) head++;
f[i]=f[q[head]]-(sumt[i]+s)*sumc[q[head]]+s*sumc[n]+sumt[i]*sumc[i];
while(head<tail&&(f[q[tail]]-f[q[tail-]])*(sumc[i]-sumc[q[tail]])>=(f[i]-f[q[tail]])*(sumc[q[tail]]-sumc[q[tail-]])) tail--;
q[++tail]=i;
}
printf("%d\n",f[n]);return ;
}
任务安排3 T可能是负数
#include<bits/stdc++.h> using namespace std; const int N=;
long long sumt[N],sumc[N],f[N];
int q[N],n,s,head,tail; int binarysearch(int i,int k){
if(head==tail) return q[head];
int l=head,r=tail;
while(l<r){
int mid=(l+r)>>;
if(f[q[mid+]]-f[q[mid]]<=k*(sumc[q[mid+]]-sumc[q[mid]])) l=mid+;
else r=mid;
}return q[l];
}
int main(){
cin>>n>>s;
for(int i=;i<=n;i++){
int t,c;
cin>>t>>c;
sumc[i]=sumc[i-]+c;
sumt[i]=sumt[i-]+t;
}
head=tail=;
for(int i=;i<=n;i++){
int p=binarysearch(i,s+sumt[i]);
f[i]=f[p]-(s+sumt[i])*sumc[p]+sumt[i]*sumc[i]+s*sumc[n];
while(head<tail&&(f[q[tail]]-f[q[tail-]])*(sumc[i]-sumc[q[tail]])>=(f[i]-f[q[tail]])*(sumc[q[tail]]-sumc[q[tail-]])) tail--;
q[++tail]=i;
}
cout<<f[n]<<endl;
return ;
}
bzoj 2726 任务安排(3)/loj 10184-10186 斜率优化的更多相关文章
-
【BZOJ 1191】 [Apio2010]特别行动队 (斜率优化)
dsy1911: [Apio2010]特别行动队 [题目描述] 有n个数,分成连续的若干段,每段的分数为a*x^2+b*x+c(a,b,c是给出的常数),其中x为该段的各个数的和.求如何分才能使得各个 ...
-
【BZOJ 1597】 [Usaco2008 Mar]土地购买 (斜率优化)
1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3601 Solved: 1322 Descrip ...
-
【BZOJ 1010】 [HNOI2008]玩具装箱toy (斜率优化)
1010: [HNOI2008]玩具装箱toy Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 9330 Solved: 3739 Descriptio ...
-
【BZOJ】1096: [ZJOI2007]仓库建设(dp+斜率优化)
http://www.lydsy.com/JudgeOnline/problem.php?id=1096 首先得到dp方程(我竟然自己都每推出了QAQ)$$d[i]=min\{d[j]+cost(j+ ...
-
bzoj 2726 任务安排
题目大意: 机器上有N个需要处理的任务,它们构成了一个序列 把这些任务分成若干批 从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti 在每批任务开始前,机器需要启动时间S,而完成这批 ...
-
[bzoj 2726] 任务安排 (斜率优化 线性dp)
3月14日第三题!!!(虽然是15号发的qwq) Description 机器上有N个需要处理的任务,它们构成了一个序列.这些任务被标号为1到N,因此序列的排列为1,2,3-N.这N个任务被分成若干批 ...
-
bzoj 2726 任务安排 斜率优化DP
这个题目中 斜率优化DP相当于存在一个 y = kx + z 然后给定 n 个对点 (x,y) 然后给你一个k, 要求你维护出这个z最小是多少. 那么对于给定的点来说 我们可以维护出一个下凸壳,因为 ...
-
[bzoj 1911][Apio 2010]特别行动队(斜率优化DP)
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1911 分析: 首先可以的到裸的方程f[i]=max{f[j]+a*(Si-Sj)^2+b*(S ...
-
【BZOJ】1911: [Apio2010]特别行动队(斜率优化dp)
题目 传送门:QWQ 分析 用$ dp[i] $ 表示前 i 个人组成的战斗力之和 然后显然$ dp[i]=Max ( dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum ...
随机推荐
-
c++ ado 调用存储过程并得到输出参数和返回值
// AccessSqlserverByAdo.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <Windows.h ...
-
设计模式之美:Singleton(单件)
索引 意图 结构 参与者 适用性 缺点 效果 相关模式 实现 实现方式(一):使用 Static 变量初始化 Singleton. 实现方式(二):使用 Lazy Initialization 来实现 ...
-
SQL SERVER获取数据库文件信息
MS SQL SERVER 获取当前数据库文件等信息,适用于多个版本: SELECT dbf.file_id AS FileID , dbf.name AS [FileName] , s.fi ...
-
C语言解析json类型数据
转自:http://buluzhai.iteye.com/blog/845404 首先感谢作者!! 我使用的是cJSON:http://sourceforge.net/projects/cjson ...
-
prmopt 提示框接收字符串,输入后按确定弹出警告框,警告内容为逆序的字符串
虽然已经找到offer,但因为公司还没安排实习,所以在学校的时间多了很多.好吧,这段时间我用来备考四级啦(好悲催,还没过),然后这一天,闲着无聊,就帮妹妹看了这样子一道题目啦. 题目内容: 编制一个从 ...
-
objective-c保护属性
#import <Foundation/Foundation.h> @interface ClassVirable : NSObject{ NSInteger year;//保护树形 } ...
-
Mysql重要配置参数的整理2
http://ssydxa219.iteye.com/category/209848 下面开始优化下my.conf文件(这里的优化只是在mysql本身的优化,之前安装的时候也要有优化) cat /et ...
-
easyui 给文本框 checkbox赋值问题
刚进公司 要做一个后台维护系统,选择easyui 从未接触过 对于页面给文本框赋值遇到一些问题 写下了来 我之前使用了好几种方式都未能成功给input 文本框赋值 第一尝试传统的JavaScript代 ...
-
CoreCLR文档翻译 - GC的设计
此文档来源于CoreCLR的BOTR(The Book of the Runtime), 点击打开原文 一切著作权归微软公司所有 GC的设计 作者: Maoni Stephens (@maoni0) ...
-
开源项目——小Q聊天机器人V1.0
小Q聊天机器人V1.0 http://blog.csdn.net/baiyuliang2013/article/details/51386281 小Q聊天机器人V1.1 http://blog.csd ...