【样例说明】
在[1，3]内，安排1上网，快乐程度为6；
在[4，7]内，安排2上网，快乐程度为10；
在[8，8]内，不安排；
在[9，9]内，安排3上网，快乐程度为6；
在[10，10]内，安排3上网，快乐程度为3；
这是使总的快乐程度达到最大的方案，对应的值是25。
【数据范围】
对于30%的数据，n<=4，所有的Mi<=5，T<=20；
对于60%的数据，n<=100，所有的Mi<=100，T<=2000；
对于100%的数据，n<=500，所有的Mi<=500，T<=500000，所有的0<C<=10^9，并保证最终解Max<=10^9。
以结束时间来dp即可 和背包没什么两样
注意其中的一个细节 因为这个wa了一次
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define LL long long #define pb push_back #define fi first #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) /////////////////////////////////// #define inf 0x3f3f3f3f #define N 1000+50 struct node { int s,e,v; }s[500000+5]; vector<int>tim[500000+5]; long long dp[500000+5]; int main() { int n,T; RII(n,T); int cnt=0; rep(i,1,n) { int q; RI(q); while(q--) { int a,b,c; RIII(a,b,c); if(b>T)continue; s[++cnt].s=a; s[cnt].e=b; s[cnt].v=c; tim[b].pb(cnt); } } rep(i,1,T) { dp[i]=dp[i-1]; if(tim[i].size() ) rep(j,0,tim[i].size()-1) { int u=tim[i][j]; dp[i]=max(dp[i],dp[i-(s[u].e-s[u].s+1)]+s[u].v );//注意这里一定要加一 举个起点和终点相等的例子即可 } } cout<<dp[T]; return 0; }