题目名称	1455. [USACO Nov13] 不设找零
输入输出	`nochange.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	13
题目来源	cqw 于2013-12-07加入
开放分组	全部用户
提交状态
分类标签	记忆化搜索搜索法动态规划
	分享题解

通过：68，提交：143，通过率：47.55%
lingyixiaoyao	100	0.036 s	0.31 MiB	C++
lingyixiaoyao	100	0.050 s	0.29 MiB	C++
lingyixiaoyao	100	0.055 s	0.29 MiB	C++
Shirry	100	0.191 s	0.25 MiB	C++
紫葉	100	0.194 s	1.20 MiB	C++
SOBER GOOD BOY	100	0.197 s	0.45 MiB	C++
Neptune	100	0.198 s	0.92 MiB	C++
Neptune	100	0.198 s	1.17 MiB	C++
Neptune	100	0.200 s	0.92 MiB	C++
Neptune	100	0.200 s	0.92 MiB	C++

本题关联比赛
20131207

关于不设找零的近10条评论(全部评论)
省选前一晚写这道题……死活都w。 Shirry 2017-04-26 10:55 11楼
我觉得评测姬抽了 XDDD 2017-04-22 22:55 10楼
直接输出的骗分，竟然有46分，我也不说啥了啊吧啦吧啦吧 2015-07-27 16:39 9楼
论O2的重要性。0.2s和0.4s。唉有整整一倍。在复赛我要纠结数据会不会故意卡STL了。 Ezio 2014-10-13 08:42 8楼
蒟蒻膜拜楼上众大神，求庇护，求灵气。 Ezio 2014-10-13 08:39 7楼
把硬币从大到小排序有利于解题。。。我改了4种算法才过的 HouJikan 2014-10-03 10:47 6楼
回复 @名扬天下G : ORZ 秒想算法的大神 cstdio 2013-12-13 19:57 5楼
回复 @cstdio : 果然我的沙茶程序被刷下去了 , 2013-12-13 19:54 4楼
必须按顺序买。 f[i]代表状态为i（用K个二进制位存储硬币的选取）时最多买到哪，记忆化宽搜，用计算出的f[i]去更新即可 cstdio 2013-12-12 18:48 3楼
回复 @你的节操碎了��地 : .................. C语言入门 2013-12-11 21:25 2楼

1455. [USACO Nov13] 不设找零

★★★ 输入文件：nochange.in 输出文件：nochange.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

FJ正在市场上为他的农场采购日用品，他口袋里有K(1<=K<=16)个硬币，每一个硬币的面值均在1～1,000,000,000之间。FJ有一个包含N(1<=N<=100,000)种待购物品的序列清单，其中第i种物品需要的钱数为c(i)，（1<=c(i)<=10,000），在购物的过程中，他随时可以停下来用一枚硬币付一次钱，每次付钱的对象为从上次付钱之后至当前所有物品价值和（当然，他所付的硬币面值也必须足够大），不巧的是，市场上的商户们都没有零钱了，因此如果FJ给的硬币面值大于所购物品价值，他也不会得到找零！

请计算FJ完成N件物品的购物后，所能剩下的最大钱数。如果他无法买到所有物品，输出-1。

【输入格式】

第1行：两个整数K，N；

第2～K+1行：每行为一个硬币面值；

第K+2～N+K+1行：这N行为FJ所要购买的N件物品的价值。

【输出格式】

一行，即结束购物后FJ所剩余的最大钱数，输出-1表示他无法完成购物。

【样例输入】

【样例输出】

12
输出解释：
FJ花费面值为10的硬币购买前两件物品，然后花费面值为15的硬币购买剩余的4样物品，最后剩余一枚面值为12的硬币。

【提示】

在此键入。

【来源】

USACO 2013 November Contest, Gold