洛谷 P2925 [USACO08DEC]干草出售Hay For Sale

缺乏、安全感 2021-11-29 09:10 227阅读 0赞

### 嗯... ###

## ##

### 题目链接：https://www.luogu.org/problemnew/show/P2925 ###

# #

## 这是一道简单的01背包问题，但是按照正常的01背包来做会TLE一个点，所以要加一个特判（见代码）。 ##

## AC代码： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 int v[50005], dp[50005]; 
     7 
     8 int main(){
     9     int c, h;
    10     scanf("%d%d", &c, &h);
    11     for(int i = 1; i <= h; i++)
    12         scanf("%d", &v[i]);
    13     for(int i = 1; i <= h; i++){
    14         for(int j = c; j >= v[i]; j--){
    15             dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
    16             if(dp[j] == c){
    17                 printf("%d", c);
    18                 return 0;
    19             }//特判 
    20         }
    21     }
    22     printf("%d\n", dp[c]);
    23     return 0;
    24 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11184974.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/d69067a74fe64ae48e76cebb9c941086.png

发表评论取消回复

表情：

评论列表（有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读

相关基础算法题——P2926 [USACO08DEC]Patting Heads S（思维转变、剪枝）

[Patting Heads S][] 今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。贝茜让 N(1 ≤ N ≤ 10 5) 头奶牛坐成一个圈。除了

柔情只为你懂/ 2022年11月22日 00:10/ 0 赞/ 115 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 319 阅读

相关洛谷P1216 [USACO1.5]数字三角形 Number Triangles

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

你的名字/ 2022年05月28日 21:19/ 0 赞/ 162 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 315 阅读

相关 Luogu P2922 [USACO08DEC]秘密消息Secret Message 字典树 Trie树

本来想找\\(01Trie\\)的结果找到了一堆字典树水题。。。算了算了当水个提交量好了。直接插入模式串，维护一个\\(Trie\\)树的子树\\(sum\\)大小，

绝地灬酷狼/ 2022年01月09日 10:49/ 0 赞/ 159 阅读

相关洛谷P2886 [USACO07NOV]牛继电器Cow Relays

题目描述 For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to r

我不是女神ヾ/ 2021年12月16日 03:01/ 0 赞/ 256 阅读

相关洛谷 P2925 [USACO08DEC]干草出售Hay For Sale

嗯... 题目链接：https://www.luogu.org/problemnew/show/P2925 这是一道简单的01背包问题，但是按照正常的

缺乏、安全感/ 2021年11月29日 09:10/ 0 赞/ 228 阅读

相关洛谷 P2746 [USACO5.3]校园网Network of Schools

题目描述一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定

不念不忘少年蓝@/ 2021年11月01日 03:24/ 0 赞/ 212 阅读

相关洛谷2850 【Usaco2006 Dec】虫洞Wormholes SPFA

问题描述 John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向

本是古典何须时尚/ 2021年09月30日 15:48/ 0 赞/ 218 阅读

相关洛谷 P2947 [USACO09MAR]仰望Look Up

题目描述 Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once a

谁践踏了优雅/ 2021年09月29日 11:28/ 0 赞/ 285 阅读