题目名称	1749. 支付宝
输入输出	`pay.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	清羽于2014-10-19加入
开放分组	全部用户
提交状态
分类标签	动态规划多重背包
	分享题解

通过：37，提交：159，通过率：23.27%
521	100	0.044 s	1.69 MiB	C++
LOSER	100	0.045 s	1.69 MiB	C++
┭┮﹏┭┮	100	0.050 s	4.43 MiB	C++
┭┮﹏┭┮	100	0.053 s	4.05 MiB	C++
Pine	100	0.062 s	29.15 MiB	C++
LGLJ	100	0.064 s	2.02 MiB	C++
瑆の時間~無盡輪迴·林蔭	100	0.064 s	11.01 MiB	C++
syzhaoss	100	0.072 s	2.25 MiB	C++
Iostream3100	100	0.083 s	23.64 MiB	C++
520	100	0.084 s	3.39 MiB	C++

关于支付宝的近10条评论(全部评论)
第一次看到神奇的P ┭┮﹏┭┮ 2023-08-02 21:35 11楼
错了这么多次，没想到竟然是数组开小了 521 2016-06-05 22:22 10楼
WW TT 2014-10-20 06:58 9楼
………… 东方老败 2014-10-19 22:13 8楼
@cstdio 已经搞定。多谢清羽 2014-10-19 21:09 7楼
回复 @cstdio : 好的，我看一下吧。其实那个插件是粘的清羽 2014-10-19 21:06 6楼
回复 @清羽 : 关于评测插件的说明在此：http://cojs.tk/cogs/page/page.php?aid=4 你写那个插件的格式貌似不对~ cstdio 2014-10-19 20:51 5楼
无奈，只好把题目改成输出字典序最小的一组解了。这样貌似就比较坑了清羽 2014-10-19 20:34 4楼
回复 @cstdio : 好吧……粘贴的评测插件真不靠谱。我再试试吧，多谢清羽 2014-10-19 20:25 3楼
回复 @清羽 : 评测插件写搓了呗…… cstdio 2014-10-19 18:50 2楼

1749. 支付宝

★★☆ 输入文件：pay.in 输出文件：pay.out 评测插件
时间限制：1 s 内存限制：128 MiB

【题目描述】

做完前七次Nescafé 模拟赛之后，你已经欠了一大笔电费。现在收电费的已经把你堵在了家里。当然了，你并不是打算一直拖欠电费的人，你只是如果不能用最少的纸币张数凑出电费金额的话会感到十分不爽。本来这是一件很简单的事，但是你平常很少使用标准的纸币，而是习惯去银行领一本支票簿，在每一张上填上自己喜欢的金额然后把这些东西用作纸币付账，这就使问题变得复杂了起来。现在你知道你一共填写了N种金额的支票，第i 种支票的金额和数目分别是Wi 和Ci，而电费的总额是K。为了尽快把收电费的打发走，你需要写一个程序，帮助你确定使用支票数目最少的支付方案。

【输入格式】

第一行是一个整数N，表示支票金额的种类数。

第二行是N 个整数W1, W2, ..., WN，表示支票的金额。

第三行是N 个整数C1, C2, ..., CN，表示支票的数目。

第四行是一个整数K，表示电费的金额。

【输出格式】

第一行输出一个整数T，表示至少需要使用的支票数目。

第二行按顺序输出N 个整数U1, U2, ..., UN。其中Ui 表示使用第i 种支票的数目。

如果有多种方案，输出任意一个即可。

【样例输入】

【样例输出】

3
1 1 1

【数据范围】

对于20% 的数据，N≤10，Wi≤500，Ci≤200，K≤2000。

对于 100% 的数据，N≤200，Wi,Ci, K≤20000。

【说明】

如果算出最少使用的支票数目，则得40%的分数；

如果全部正确，则得100%得分数。