POJ 3616 DP - c++编程基础

题意：给你N的时间，M的工作时间段，每个时间段有一个权重，还有一个R，每次完成一个工作需要休息R，问最后在时间N内，最大权重是多少。

思路：很简单的DP，首先对区间的右坐标进行排序，然后直接转移方程就是dp[i] = max(dp[i] , dp[j] + work[i].c) ，判断条件就是这两个区间加上一个休息时间R是否会相交。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
using namespace std;  
  
int n , m , r ;  
struct WORK{  
    int s , e , c ;  
}work[1111] ;  
int dp[1111] ;  
bool cmp(const WORK &x ,const WORK & y){  
    return x.e < y.e ;  
}  
int main() {  
    while(cin >




> n >> m >> r){  
        mem(dp ,0) ;  
        for (int i = 0 ; i < m ; i ++ ){  
            scanf("%d%d%d",&work[i].s , &work[i].e , &work[i].c) ;  
        }  
        sort(work , work + m , cmp) ;  
        int ans = 0 ;  
        for (int i = 0 ; i < m ; i ++ ){  
            dp[i] = max(dp[i] , work[i].c) ;  
        }  
        for (int i = 0 ; i < m ; i ++ ){  
            for (int j = 0 ; j < i ; j ++ ){  
                int rev = work[j].e + r ;  
                if(work[i].s >= rev){  
                    dp[i] = max(dp[i] , dp[j] + work[i].c) ;  
                }  
                ans = max(ans , dp[i]) ;  
            }  
        }  
        cout << ans << endl;  
    }  
    return 0;  
}