| 题目名称 | 2254. 买汽水 |
|---|---|
| 输入输出 | drink.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2016-04-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：56， 提交：136， 通过率：41.18% | ||||
 ☬Hero Vanleto |
100 | 0.002 s | 0.28 MiB | C++ |
 Yuri |
100 | 0.002 s | 0.29 MiB | C++ |
 Sky_miner |
100 | 0.002 s | 0.29 MiB | C++ |
 MistyEye |
100 | 0.002 s | 0.31 MiB | C++ |
 浮生随想 |
100 | 0.002 s | 0.31 MiB | C++ |
 咸鱼二号 |
100 | 0.002 s | 0.31 MiB | C++ |
 Hale |
100 | 0.002 s | 0.31 MiB | C++ |
 HeHe |
100 | 0.002 s | 0.57 MiB | C++ |
 kZime |
100 | 0.002 s | 0.57 MiB | C++ |
 destiny |
100 | 0.003 s | 0.25 MiB | C++ |
| 本题关联比赛 | |||
| 20160420s | |||
| 关于 买汽水 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
要是m<=1e+8，我有一个O((n/2)*2^(n/2))的算法，空间复杂度是O(m)，半dp半搜索，最后来个二分。如果m太大的话还得hash或者平衡树，可能复杂度会挂。
| ||||
|
谁说的m<=1e+8，真是坑啊
| ||||
|
| ||||
|
| ||||
|
学姐，我看到你了，@_Horizon
| ||||
|
数组开小了QAQ
| ||||
FoolMike
SOBER GOOD BOY
_Horizon【题目描述】
czyz 暑期集训一共 N 天。由于 jmy 和 lkf 玩游戏总是输，作为惩罚，他需要给 oiers 买汽水。
jmy 最多只能给大家花 M 元钱。由于每天汽水的价格都不固定，现在给出每天买汽水的花销，我们可以随意选择让 jmy 哪些天买汽水（当然总花费不能超过 M）。请问最多一共能够花掉 jmy 多少钱呢？
假设：暑假最多不超过 40 天，jmy 给大家花的钱最多有一亿。
【输入格式】
输入第一行有两个整数 N，M。 1<=N<=40，0<=M<=100,000,000。
接下来一行有 N 个数，第 i 个数表示第 i 天的汽水花销。每天汽水的花销 p<=100,000,000。
【输出格式】
输出一行一个整数，表示我们最多能够花掉 jmy 多少钱。
【样例1】
输入 3 10 1 2 3 输出 6
【样例2】
输入 4 10 4 3 5 11 输出 9
【提示】
【数据规模】
对于 10%的数据，N<=10；
对于 30%的数据，N<=20；
对于 60%的数据，N<=30；
对于 100%的数据，N<=40。
【来源】
在此键入。