题目大意：要用N种材料建一条长为L的路，如今给出每种材料的长度w。起始地点x。发费c和耐久度f

问：在预算为B的情况下，建好这条路的最大耐久度是多少

解题思路：背包问题

dp[i][j]表示起始地点为i。发费为j的最大耐久度

可得转移方程

dp[i + w][j + c] = max(dp[i + w][j + c],dp[i][j] + f)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxl 1010

#define maxn 10010

#define INF 0x3f3f3f3f

int L, N, B;

int dp[maxl][maxl];

struct component {

    int x, w, f, c;

}com[maxn];

int cmp(const component a, const component b) {

    return a.x < b.x;

}

void init() {

    for(int i = 0; i < N; i++)

        scanf("%d%d%d%d", &com[i].x, &com[i].w, &com[i].f, &com[i].c);

    sort(com, com + N, cmp);

}

void solve() {

    memset(dp, -1, sizeof(dp));

    dp[0][0] = 0;

    for(int i = 0; i < N; i++) {

        for(int j = 0; j <= B - com[i].c; j++)

            if(dp[com[i].x][j] != -1) {

                dp[com[i].x + com[i].w][j + com[i].c] = max(dp[com[i].x + com[i].w][j + com[i].c], dp[com[i].x][j] + com[i].f) ;

            }

    }

    int ans = -1;

    for(int i = 0; i <= B; i++)

        if(dp[L][i] != INF)

            ans = max(ans, dp[L][i]);

    printf("%d\n", ans);

}

int main() {

    while(scanf("%d%d%d", &L, &N, &B) != EOF ) {

        init();

        solve();

    }

    return 0;

}