格式原因直接挂链接：http://www.tyvj.cn/Problem_Show.aspx?id=1034
经典ACM题目，最近为了练习DP必须要做的。
题目的要求很简单，有n个进行的任务，如果某时刻如果有任务必须完成，有多个任务在同一时刻开始则选一个进行，没有的话就休息。求最大的休息时间。
尼克有两种状态可以选择：休息，选择手上的任务并做完其中一个。设f[i]是后i分钟可以获得的最大空闲时间，可以很容易得到f[i]=f[i+1]+1（没有任务，可以休息），f[i]=max{f[i+a[i][j]]}（a[i][j]代表i时刻开始的第j个任务的持续时间），然后问题就解决了。
为什么要逆序DP呢？因为不难发现，选择是在任务的开始，不是任务的结束，要在同一起始点转移状态，必将从后往前，所以就有了本方法。编程方面要注意的是如果开10000*10000的数组就会悲剧，但是本着“面向数据编程”的态度，可以发现，开10000*2000就够了，这个数据范围放在这里是不准确的，考试应该不会遇到这种情况。遇到了就只有跪了……
当然，本题还可以用最短路实现，这里不再赘述。
View Code 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int MAXN = 10010; 9 const int MAXLST = 5010; 10 11 int task[MAXN], f[MAXN], time[MAXN][MAXLST]; 12 int n, k; 13 14 int main() { 15 scanf("%d%d", &n, &k); 16 for (int i = 1; i <= k; i ++) { 17 int x, y; 18 scanf("%d", &x); 19 task[x] ++; 20 scanf("%d", &y); 21 time[x][ task[x] ] = y; 22 } 23 24 for (int i = n; i >= 1; i --) { 25 if (!task[i]) { 26 f[i] = f[i + 1] + 1; 27 } else { 28 for (int j = 1; j <= task[i]; j ++) 29 f[i] = max(f[i], f[ i + time[i][j] ]); 30 } 31 } 32 33 printf("%d\n", f[1]); 34 35 return 0; 36 }转载于:https://www.cnblogs.com/stickjitb/archive/2012/10/01/2709984.html
