bzoj 2726 任务安排(3)/loj 10184-10186 斜率优化

时间:2022-09-08 19:14:15

任务安排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 斜率优化的更多相关文章

  1. 【BZOJ 1191】 &lbrack;Apio2010&rsqb;特别行动队 (斜率优化)

    dsy1911: [Apio2010]特别行动队 [题目描述] 有n个数,分成连续的若干段,每段的分数为a*x^2+b*x+c(a,b,c是给出的常数),其中x为该段的各个数的和.求如何分才能使得各个 ...

  2. 【BZOJ 1597】 &lbrack;Usaco2008 Mar&rsqb;土地购买 (斜率优化)

    1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 3601  Solved: 1322 Descrip ...

  3. 【BZOJ 1010】 &lbrack;HNOI2008&rsqb;玩具装箱toy (斜率优化)

    1010: [HNOI2008]玩具装箱toy Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 9330  Solved: 3739 Descriptio ...

  4. 【BZOJ】1096&colon; &lbrack;ZJOI2007&rsqb;仓库建设(dp&plus;斜率优化)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1096 首先得到dp方程(我竟然自己都每推出了QAQ)$$d[i]=min\{d[j]+cost(j+ ...

  5. bzoj 2726 任务安排

    题目大意: 机器上有N个需要处理的任务,它们构成了一个序列 把这些任务分成若干批 从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti 在每批任务开始前,机器需要启动时间S,而完成这批 ...

  6. &lbrack;bzoj 2726&rsqb; 任务安排 (斜率优化 线性dp)

    3月14日第三题!!!(虽然是15号发的qwq) Description 机器上有N个需要处理的任务,它们构成了一个序列.这些任务被标号为1到N,因此序列的排列为1,2,3-N.这N个任务被分成若干批 ...

  7. bzoj 2726 任务安排 斜率优化DP

    这个题目中 斜率优化DP相当于存在一个 y = kx + z 然后给定 n 个对点 (x,y)  然后给你一个k, 要求你维护出这个z最小是多少. 那么对于给定的点来说 我们可以维护出一个下凸壳,因为 ...

  8. &lbrack;bzoj 1911&rsqb;&lbrack;Apio 2010&rsqb;特别行动队(斜率优化DP)

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1911 分析: 首先可以的到裸的方程f[i]=max{f[j]+a*(Si-Sj)^2+b*(S ...

  9. 【BZOJ】1911&colon; &lbrack;Apio2010&rsqb;特别行动队(斜率优化dp)

    题目 传送门:QWQ 分析 用$ dp[i] $ 表示前 i 个人组成的战斗力之和 然后显然$ dp[i]=Max (  dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum ...

随机推荐

  1. c&plus;&plus; ado 调用存储过程并得到输出参数和返回值

    // AccessSqlserverByAdo.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <Windows.h ...

  2. 设计模式之美:Singleton(单件)

    索引 意图 结构 参与者 适用性 缺点 效果 相关模式 实现 实现方式(一):使用 Static 变量初始化 Singleton. 实现方式(二):使用 Lazy Initialization 来实现 ...

  3. SQL SERVER获取数据库文件信息

        MS SQL SERVER 获取当前数据库文件等信息,适用于多个版本: SELECT dbf.file_id AS FileID , dbf.name AS [FileName] , s.fi ...

  4. C语言解析json类型数据

    转自:http://buluzhai.iteye.com/blog/845404   首先感谢作者!! 我使用的是cJSON:http://sourceforge.net/projects/cjson ...

  5. prmopt 提示框接收字符串,输入后按确定弹出警告框,警告内容为逆序的字符串

    虽然已经找到offer,但因为公司还没安排实习,所以在学校的时间多了很多.好吧,这段时间我用来备考四级啦(好悲催,还没过),然后这一天,闲着无聊,就帮妹妹看了这样子一道题目啦. 题目内容: 编制一个从 ...

  6. objective-c保护属性

    #import <Foundation/Foundation.h> @interface ClassVirable : NSObject{ NSInteger year;//保护树形 } ...

  7. Mysql重要配置参数的整理2

    http://ssydxa219.iteye.com/category/209848 下面开始优化下my.conf文件(这里的优化只是在mysql本身的优化,之前安装的时候也要有优化) cat /et ...

  8. easyui 给文本框 checkbox赋值问题

    刚进公司 要做一个后台维护系统,选择easyui 从未接触过 对于页面给文本框赋值遇到一些问题 写下了来 我之前使用了好几种方式都未能成功给input 文本框赋值 第一尝试传统的JavaScript代 ...

  9. CoreCLR文档翻译 - GC的设计

    此文档来源于CoreCLR的BOTR(The Book of the Runtime), 点击打开原文 一切著作权归微软公司所有 GC的设计 作者: Maoni Stephens (@maoni0) ...

  10. 开源项目——小Q聊天机器人V1&period;0

    小Q聊天机器人V1.0 http://blog.csdn.net/baiyuliang2013/article/details/51386281 小Q聊天机器人V1.1 http://blog.csd ...