题目P2639 [USACO09OCT] Bessie’s Weight Problem G题目描述Bessie 像她的诸多姊妹一样因为从 Farmer John 的草地吃了太多美味的草而长出了太多的赘肉。所以 FJ 将她置于一个及其严格的节食计划之中。她每天不能吃多过H ( 5 ≤ H ≤ 45 , 000 ) H (5 \le H \le 45,000)H(5≤H≤45,000)公斤的干草。 Bessie 只能吃一整捆干草当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N ( 1 ≤ N ≤ 500 ) N (1 \le N \le 500)N(1≤N≤500)捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地每捆干草只能被吃一次即使在列表中相同的重量可能出现2 22次但是这表示的是两捆干草其中每捆干草最多只能被吃掉一次。 给定一个列表表示每捆干草的重量S i ( 1 ≤ S i ≤ H ) S_i (1 \le S_i \le H)Si​(1≤Si​≤H), 求 Bessie 不超过节食的限制的前提下可以吃掉多少干草注意一旦她开始吃一捆干草就会把那一捆干草全部吃完。输入格式第一行有两个由空格隔开的整数H HH和N NN。第2 22到第N 1 N1N1行第i 1 i1i1行是一个单独的整数表示第i ii捆干草的重量S i S_iSi​。输出格式第一行一个单独的整数表示 Bessie 在限制范围内最多可以吃多少公斤的干草。输入输出样例 #1输入 #156 4 15 19 20 21输出 #156说明/提示输入说明有四捆草重量分别是15 , 19 , 20 15,19,2015,19,20和21 2121。Bessie 在56 5656公斤的限制范围内想要吃多少就可以吃多少。输出说明Bessie 可以吃3 33捆干草重量分别为15 , 20 , 21 15, 20, 2115,20,21。恰好达到她的56 5656公斤的限制。代码1二维数组#includebits/stdc.husingnamespacestd;constintN50010,M4500010;intn,V,v,f[N][M];intmain(){cinVn;for(inti1;in;i){cinv;for(intj0;jV;j){f[i][j]f[i-1][j];if(vj)f[i][j]max(f[i][j],f[i-1][j-v]v);}}coutf[n][V];return0;}代码2一维数组#includebits/stdc.husingnamespacestd;constintM4500010;intn,V,v,f[M];intmain(){cinVn;for(inti1;in;i){cinv;for(intjV;jv;j--){f[j]max(f[j],f[j-v]v);}}coutf[V];return0;}结果