首页 > 代码库 > [luoguP2854] [USACO06DEC]牛的过山车Cow Roller Coaster(DP + sort)
[luoguP2854] [USACO06DEC]牛的过山车Cow Roller Coaster(DP + sort)
传送门
先按照起点 sort 一遍。
这样每一个点的只由前面的点决定。
f[i][j] 表示终点为 i,花费 j 的最优解
状态转移就是一个01背包。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 int L, N, B; 7 int f[10001][1001]; 8 9 inline int read()10 {11 int x = 0, f = 1;12 char ch = getchar();13 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;14 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;15 return x * f;16 }17 18 struct node19 {20 int x, w, f, c;21 }p[10001];22 23 inline bool cmp(node x, node y)24 {25 return x.x < y.x;26 }27 28 inline int max(int x, int y)29 {30 return x > y ? x : y;31 }32 33 int main()34 {35 int i, j;36 L = read();37 N = read();38 B = read();39 for(i = 1; i <= N; i++)40 {41 p[i].x = read();42 p[i].w = read();43 p[i].f = read();44 p[i].c = read();45 p[i].w += p[i].x;46 }47 std::sort(p + 1, p + N + 1, cmp);48 memset(f, -1, sizeof(f));49 for(i = 0; i <= B; i++) f[0][i] = 0;50 for(i = 1; i <= N; i++)51 for(j = B; j >= p[i].c; j--)52 if(f[p[i].x][j - p[i].c] ^ -1)53 f[p[i].w][j] = max(f[p[i].w][j], f[p[i].x][j - p[i].c] + p[i].f);54 printf("%d\n", f[L][B]);55 return 0;56 }
[luoguP2854] [USACO06DEC]牛的过山车Cow Roller Coaster(DP + sort)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。