Summary:

1. Fill dp array explicitly by using dp[i] = dp[i+1]

2. At time i, do the first job explicitly

 

Code:

/* * source.cpp * *  Created on: Apr 5, 2014 *      Author: sangs */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;class Job {public:	int st, ed, duration;	Job(int _st, int _ed, int _du):st(_st), ed(_ed), duration(_du) {}	Job() {		st = ed = duration = 0;	}};vector
          
            jobs[2500];int dp[2500];int cal(int n) { memset(dp, 0, sizeof(dp)); for(int i = n; i >= 0; i --) { if(jobs[i].size() == 0) { dp[i] = dp[i+1]; continue; } int du = jobs[i][0].duration; dp[i] = du + dp[i+du]; for(size_t j = 1; j < jobs[i].size(); j ++) { du = jobs[i][j].duration; dp[i] = min(dp[i], du+dp[i+du]); } } for(int i = 0; i <= n; i ++) jobs[i].clear(); return dp[0];}int main() { freopen("input.txt", "r", stdin); int cases, m; scanf("%d", &cases); while(cases --) { scanf("%d", &m); int n = 0; for(int i = 0; i < m; i ++) { int st, ed, du; scanf("%d%d%d", &du, &st, &ed); n = max(n, ed); for(int j = st; j <= ed-du; j ++) { jobs[j].push_back(Job(st, ed, du)); } } int res = cal(n); printf("%d\n", res); } return 0;}