Cogs 376. [IOI2002]任务安排(后效性DP)
2024-09-22 14:32:55
- [IOI2002]任务安排
★☆ 输入文件:batch.in 输出文件:batch.out 简单对比
时间限制:1 s 内存限制:128 MB
N个任务排成一个序列在一台机器上等待完成(顺序不得改变),这N个任务被分成若干批,每批包含相邻的若干任务。从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti。在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成)。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案,使得总费用最小。
例如:S=1;T={1,3,4,2,1};F={3,2,3,3,4}。如果分组方案是{1,2}、{3}、{4,5},则完成时间分别为{5,5,10,14,14},费用C={15,10,30,42,56},总费用就是153。
输入
第一行是N(1<=N<=5000)。
第二行是S(0<=S<=50)。
下面N行每行有一对数,分别为Ti和Fi,均为不大于100的正整数,表示第i个任务单独完成所需的时间是Ti及其费用系数Fi。
输出
一个数,最小的总费用。
输入样例
5
1
1 3
3 2
4 3
2 3
1 4
输出样例
153
/*
DP.
n^2做法.
这题没想出来.
正解要考虑后效性.
因为当我们选择一个任务作为开始的时候
它必然会对后面的决策产生影响.
所以我们先把后效性的贡献算出来累加进去.
方程长这样
f[i]=min(f[i],f[j-1]+(sumw[i]-sumw[j-1])*sumt[i]+S*(sumw[n]-sumw[j-1]))
sumw表示前缀F[i],sumt表示前缀t[i].
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 5010
using namespace std;
int n,S,F[MAXN],f[MAXN],sumt[MAXN],sumw[MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void slove()
{
for(int i=1;i<=n;i++) f[i]=1e9;
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
f[i]=min(f[i],f[j-1]+(sumw[i]-sumw[j-1])*sumt[i]+S*(sumw[n]-sumw[j-1]));
}
printf("%d",f[n]);
}
int main()
{
freopen("batch.in","r",stdin);
freopen("batch.out","w",stdout);
int x;
n=read(),S=read();
for(int i=1;i<=n;i++)
{
x=read(),F[i]=read();
sumt[i]=sumt[i-1]+x;
sumw[i]=sumw[i-1]+F[i];
}
slove();
return 0;
}
最新文章
- C++_系列自学课程_第_11_课_类型转换_《C++ Primer 第四版》
- 如何处理C#的HttpWebResponse的GetResponse中的超时异常
- iNeedle系统使用注意事项
- RabbitMQ与Redis队列对比
- Java学习路线图
- sudo: /etc/sudoers is mode 0777, should be 0440终极解决之道
- iMx280A测试声纹
- codevs4817 江哥的dp题d
- [Lonlife1031]Bob and Alice are eating food(递推,矩阵快速幂)
- Chrome系列 Failed to load resource: net::ERR_CACHE_MISS
- 利用GPS获取行车速度和距离
- ASP.NET自定义控件组件开发 第三章 为控件添加事件 后篇
- str.方法的整理(字符串类型内置方法的具体使用)
- .NET Core微服务之基于EasyNetQ使用RabbitMQ消息队列
- MessengerJS
- java-面向对象(公元2017-6-28)
- 微信小程序开发笔记02
- JavaScript中==和===的区别(面试题目)
- promise 承诺
- C 标准库 - string.h之memmove使用
热门文章
- Luogu4827 Crash的文明世界 组合、树形DP
- 使用lxml解析HTML代码
- docker postgres 导出导入数据
- ASP.NET Core &; 双因素验证2FA 实战经验分享
- Description Resource Path Location Type Unknown Unknown Unknown	org.eclipse.core.internal.resources.Marker is not of a displayable type
- Java序列化流
- Java调用WebService方法总结(3)--wsimport调用WebService
- 基于JMeter的Quick Easy FTP Server性能测试
- dom 页面位置和大小,元素的位置和大小,鼠标位置
- javascript原型链[图]