題意：
很多人這題題目讀不懂，我詳細(xì)解釋下：一個(gè)懶工人，他想工作的時(shí)間盡量少。有N個(gè)任務(wù)，每個(gè)任務(wù)有開始時(shí)間和deadline，工人完成這個(gè)工作需要ti時(shí)間。如果某個(gè)時(shí)刻有工作可以做（這里是說，如果從這個(gè)時(shí)刻開始某個(gè)工作，在deadline之前能夠完成)，那么這個(gè)工人必須做，但是如果這個(gè)時(shí)刻存在著多余1件工作可以做，工人可以選擇；假設(shè)這個(gè)時(shí)刻沒有工作可以做了，工人就可以偷懶直到有新的任務(wù)到來。
解法：
這題初看覺得很麻煩，但是題目中有句話太給力了！
You should note that for each job i, the length of Ii, di - ai, is greater than or equal to ti, but less than 2*ti
這句話把后效性全部消除了，即不可能出現(xiàn)這種情況，在t1這個(gè)決策點(diǎn)出現(xiàn)了第k個(gè)工作，在t1后的某個(gè)決策點(diǎn)t2又出現(xiàn)了第k個(gè)工作，明白了？
DP方程：
dp[t]=min(work[i]+dp[t+work[i]]) work指在第t個(gè)時(shí)間點(diǎn)能夠可以開始做的工作
如果在第t個(gè)時(shí)刻沒有任務(wù)可做，那么dp[t]=dp[t+1]
代碼：
1 //============================================================================
2 // Name : pku1337.cpp
3 // Author : yzhw
4 // Version :
5 // Copyright : yzhw
6 // Description : Hello World in C++, Ansi-style
7 //============================================================================
8
9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <cstring>
13 using namespace std;
14 vector<int> work[251];
15 int data[101][3],n,minnum,maxnum,dp[300];
16 int getdp(int t)
17 {
18 if(t>maxnum) return 0;
19 else return dp[t];
20 }
21 int main() {
22 int test;
23 cin>>test;
24 while(test--)
25 {
26 cin>>n;
27 minnum=300;
28 maxnum=-1;
29 for(int i=0;i<=250;i++)
30 work[i].clear();
31 for(int i=0;i<n;i++)
32 {
33 cin>>data[i][0]>>data[i][1]>>data[i][2];
34 for(int j=data[i][1];j+data[i][0]<=data[i][2];j++)
35 work[j].push_back(i);
36 minnum=min(minnum,data[i][1]);
37 maxnum=max(maxnum,data[i][2]-data[i][0]);
38 }
39 memset(dp,0,sizeof(dp));
40 for(int t=maxnum;t>=minnum;t--)
41 if(work[t].empty())
42 dp[t]=dp[t+1];
43 else
44 {
45 dp[t]=data[work[t][0]][0]+getdp(data[work[t][0]][0]+t);
46 for(int i=1;i<work[t].size();i++)
47 dp[t]=min(dp[t],data[work[t][i]][0]+getdp(data[work[t][i]][0]+t));
48 }
49 cout<<dp[minnum]<<endl;
50 }
51 return 0;
52 }
53