尼克的任务
尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些
邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个
开始时刻与一个持续时间构成。
尼克的一个工作日为 N 分钟，从第一分钟开始到第 N 分钟结束。当尼
克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成，
尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如
果只有一个任务，则该任务必需由尼克去完成，假如某些任务开始时
刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第
P 分钟开始，持续时间为 T 分钟，则该任务将在第 P+T-1 分钟结束。
写一个程序计算尼克应该如何选取任务，才能获得最大的空暇时间。
tyvj10
我们可以
f[i] 表示从第1分钟到第i分钟，最多能休息多长时间
要求，第i分钟空闲或者在第i分钟刚好结束一个任务
则f[n]就是答案
但好像不能转移
则我们可以反着考虑
f[i] 表示从第i分钟到第n分钟，最多能休息多长时间
则f[1]就是答案
①若果第i分钟没有任务，则f[i]=f[i+1]+1,就是我能比后一分钟多休息1分钟；
②在第i分钟有开始的任务，结束时间为end[k] 则f[i] = max(f[end[k]+1])，就是我从工作结束后的时间找能休息最多的时间
则就可以写出代码：
......少女祈祷中
#include <cstdio> #include <algorithm> using namespace std; int dp[10010]; int n,m;int cnt=1; struct data { int end,begin; friend bool operator <(data a,data b) { return a.begin>b.begin; } }a[10010]; int poi[10010]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { scanf("%d%d",&a[i].begin,&a[i].end); poi[a[i].begin]++; //poi记录每个工作开始时间的个数 } sort(a+1,a+1+m); for(int i=n;i>=1;--i) { if(poi[i]==0) dp[i]=dp[i+1]+1; //状态①，没工作时 else for(int j=1;j<=poi[i];++j) //状态② { if(dp[i+a[cnt].end]>dp[i]) dp[i]=dp[i+a[cnt].end]; //枚举每个工作结束时能休息的时间的max cnt++; } } printf("%d",dp[1]); }