题目大意：要用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)
;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;}
可你仍然感谢天地和人世所带来的这些变化和发生。
