注意0，1，.....,N是时间点，i~i+1是时间段
然后就是思路：dp[i]代表到时间点 i 获得的最大价值，
1：dp[i]=max(dp[i],dp[s-r]+e)，表示有以s为开头,i为结尾的工作时间，效率是e（保证前面有工作）
2：dp[i]=max(dp[i],e),表示前面没有工作
3：dp[i]=max(dp[i],dp[i-1]),保存到时间点i的最大价值
代码如下
#include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<iostream> #include<cstdlib> #include<queue> #include<map> #include<set> using namespace std; typedef long long LL; struct asd { int s,e; }; vector<asd>a[1000001]; int dp[1000001]; int main() { int n,m,r; scanf("%d%d%d",&n,&m,&r); for(int i=0; i<m; ++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[y].push_back((asd) { x,z }); } for(int i=1; i<=n; ++i) { for(int j=0; j<a[i].size(); ++j) { int e=a[i][j].e; int s=a[i][j].s; dp[i]=max(dp[i],e); dp[i]=max(dp[i],dp[s-r]+e); } dp[i]=max(dp[i],dp[i-1]); } printf("%d\n",dp[n]); return 0; }
原文：http://www.cnblogs.com/shuguangzw/p/5031146.html
