# 整数的拆分和求和，如何使用动规来实现，动归解决数组问题，C语言

Problem Description
You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs p dollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.

For example, if p=17 and you have two \$10 coins, four \$5 coins, and eight \$1 coins, you will pay it by two \$5 coins and seven \$1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.

Input
The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number ci means how many coins/banknotes in denominations of i dollars in your wallet.

1≤T≤20000
0≤p≤109
0≤ci≤100000

Output
For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output '-1'.

Sample Input
3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0

Sample Output
9
-1
36

• 写回答

#### 2条回答默认 最新

• threenewbee 2019-10-04 08:16
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 eclipse无法正常运行
• ¥15 定义了函数，但是无法根据函数定义触发器
• ¥20 5变量卡诺图化简得出与非门电路图
• ¥15 Python爬取交通拥堵指数数据
• ¥15 使用vba抓取重定向网页问题
• ¥20 付费需求测试程序（细谈）。
• ¥15 为什么这段c++代码会报这么多语法错误？
• ¥20 如何利用C语言实现用最小二乘法选配两个经验公式
• ¥50 vue-codemirror如何对指定行 指定位置的 字符进行背景颜色或者字体颜色的修改？
• ¥30 遇到一个的问题，请教各位