洛谷P1280 尼克的任务 [DP补完计划]
2024-08-31 04:18:35
题目描述
尼克每天上班之前都连接上英特网,接收他的上司发来的邮件,这些邮件包含了尼克主管的部门当天要完成的全部任务,每个任务由一个开始时刻与一个持续时间构成。
尼克的一个工作日为N分钟,从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只有一个任务,则该任务必需由尼克去完成,假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的同事完成。如果某任务于第P分钟开始,持续时间为T分钟,则该任务将在第P+T-1分钟结束。
写一个程序计算尼克应该如何选取任务,才能获得最大的空暇时间。
输入输出格式
输入格式:
输入数据第一行含两个用空格隔开的整数N和K(1≤N≤10000,1≤K≤10000),N表示尼克的工作时间,单位为分钟,K表示任务总数。
接下来共有K行,每一行有两个用空格隔开的整数P和T,表示该任务从第P分钟开始,持续时间为T分钟,其中1≤P≤N,1≤P+T-1≤N。
输出格式:
输出文件仅一行,包含一个整数,表示尼克可能获得的最大空暇时间。
输入输出样例
输入样例#1: 复制
15 6
1 2
1 6
4 11
8 5
8 1
11 5
输出样例#1: 复制
4
分析:很明显的动规,从前往后肯定不好做,那么就逆向推导,可以得到,设dp[i]为i时间可获得的最大休息时间,如果当前时段有任务可做,则dp[i]=max(dp[i],dp[i+t[i]]);如果没有任务可做,则dp[i]=dp[i+1]+1。
Code:
#include<bits/stdc++.h>
#define Fi(i,a,b) for(int i=a;i<=b;i++)
#define Fx(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e4+;
int n,m,dp[N],num[N],cnt=;
struct Node{int v,t;}a[N];
bool cmp(Node x,Node y){return x.v>y.v;}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;memset(dp,,sizeof(dp));
memset(num,,sizeof(num));
Fi(i,,m){cin>>a[i].v>>a[i].t;num[a[i].v]++;}
sort(a+,a+m+,cmp);
Fx(i,n,){if(!num[i])dp[i]=dp[i+]+;
else Fi(j,,num[i]){
dp[i]=max(dp[i],dp[i+a[cnt].t]);cnt++;}
}
cout<<dp[]<<endl;return ;
}
最新文章
- JS技术大全(防止复制,粘贴等)
- TCL:使用、添加库文件
- iOS 小经验:UIAnimation空对象导致crash
- android XMl 解析神奇xstream 四: 将复杂的xml文件解析为对象
- Codebook model 视频抠像 xp sp3 + vs2005 + OpenCV 2.3.1
- android JSON 技术
- JavaScript修改表中的内容
- 转:基于科大讯飞语音API语音识别开发详解
- 利用python进行数据分析之数据聚合和分组运算
- 【2017-2-17】VS基本应用及C#基础第一节(定义变量、输入及输出)
- Hibernate中调用带有underscore的Column Name
- Centos6.5 登录时,提示Module is unkown
- Spring Cloud Context模块
- java完整并发知识结构图
- CentOS7.3安装Go运行和开发环境
- linux之常见错误
- phpmyadmin-您可能正在上传很大的文件,请参考文档来寻找解决方法
- PHP类的继承
- C#winform使用进度条
- cocos2d-js 3.0 rc0 编译release报错 value for keystore is not valid. it must resolve to a single path
热门文章
- How to Disable System Integrity Protection (rootless) in OS X El Capitan
- mongo在centos与windows上部署与配置,及远程连接mongo与数据用户和角色分配
- iOS通知传值
- PHP 截取字符串,多余部分用 ........ 代替
- 【BZOJ】1577: [Usaco2009 Feb]庙会捷运Fair Shuttle
- 【BZOJ】1609: [Usaco2008 Feb]Eating Together麻烦的聚餐
- Mac 上真机调试cocos2d-x-3.16的test程序
- js_判断当前url是否合法http(s)
- js_参数的get传输,从一个页面到另外一个页面。
- 常见网络命令之traceroute命令一起其他常用命令