临海门户网站住房和城乡建设规划局,腾讯视频推广联盟,外贸海外网站推广,php做动漫网站题目大意#xff1a;要用N种材料建一条长为L的路#xff0c;如今给出每种材料的长度w。起始地点x。发费c和耐久度f 问#xff1a;在预算为B的情况下#xff0c;建好这条路的最大耐久度是多少 解题思路#xff1a;背包问题 dp[i][j]表示起始地点为i。发费为j的最大耐久度… 题目大意要用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) #includecstdio
#includecstring
#includealgorithm
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;
}
