题意:给你N的时间,M的工作时间段,每个时间段有一个权重,还有一个R,每次完成一个工作需要休息R,问最后在时间N内,最大权重是多少。
思路:很简单的DP,首先对区间的右坐标进行排序,然后直接转移方程就是dp[i] = max(dp[i] , dp[j] + work[i].c) ,判断条件就是这两个区间加上一个休息时间R是否会相交。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #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<int,int> #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; }