https://ac.nowcoder.com/acm/contest/318/J

题解：

时间可以任意安排，只需要考虑时长即可

本题为一个裸的01背包，背包的大小为T-S。
第i 个时间段可以看成一个物品，这个物品的体积w[i]=b[i]-a[i]，价值v[i] 为熟练度c。那么dp[i][j]就表示着在前i 个时间段里花费j 的时间练英雄能得到的最大熟练度。
状态转移方程为:

For i = 1;i <= n;i++
    For j = w[i];j <= sum;j++
        dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);


当然也可以考虑用滚动数组来优化一下空间复杂度，此时的状态转移方程为：
 

For i = 1;i <= n;i++
    For j = sum;j >= w[i];j--
        dp[j] = max(dp[j],dp[j-w[i]]+v[i]);

C++版本一 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q,s;
int w[N];
int v[N];
ll dp[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif


    while(~scanf("%d%d%d",&n,&s,&t)){
        int a,b;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&a,&b,&w[i]);
            v[i]=b-a;
            for(int j=t-s;j>=v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        printf("%lld\n",dp[t-s]);
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<cstdlib>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<time.h>
#include<deque>
#define bug printf("*********\n");
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9+7;
const LL INF = 1e9+7;
const int base = 131;
const double pi = 3.1415926;
const double eps = 0.000000001;

int n, S, T;
LL dp[1010], w[1010], v[1010];

int main() {
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int a, b;
    while(~scanf("%d%d%d", &n, &S, &T)) {
        mem0(dp);
        int sum = T-S;
        for(int i = 0; i < n; i ++) {
            scanf("%d%d%d", &a, &b, &v[i]);
            w[i] = b-a;
        }
        for(int i = 0; i < n; i ++) {
            for(int j = sum; j >= w[i]; j --) {
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            }
        }
        printf("%lld\n", dp[sum]);
    }
#ifndef ONLINE_JUDGE
    cout <<"It costs " <<clock() <<" ms\n";
#endif
    return 0;
}