[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 17 18 struct node 19 p[10001]; 22 23 inline bool cmp(node x, node y) 24 27 28 inline int max(int x, int y) 29 32 33 int main() 34 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]; j) 52 if(f[p[i].x][j p[i]] ^ 1) 53 f[p[i].w][j] = max(f[p[i].w][j], f[p[i].x][j p[i]] + p[i].f); 54 printf("%d\n", f[L][B]); 55 return 0; 56 }
View Code

上一篇：[luoguP2863] [USACO06JAN]牛的舞会The Cow Prom（Tarjan）

下一篇：[luoguP2701] [USACO5.3]巨大的牛棚Big Barn（DP）

---

stl DP