编程介的小学生 2019-01-05 00:40 采纳率: 6.8%
浏览 757
已采纳

整数的拆分和求和,如何使用动规来实现,动归解决数组问题,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
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 跑hls xfopencv的例程standalone_hls_axi_example出的错误,csim没问题,c synthesis出的错误
  • ¥15 sqlserver update语句逐行生效
  • ¥15 mssql2000游标循环次数对不上
  • ¥20 Windows10系统命令行调用
  • ¥15 php环境如何实现国密SM2相关功能
  • ¥15 关于#单片机#的问题:K210 例程里面提示我iomem.h: No such file or directory
  • ¥15 LSPI算法的大问题
  • ¥15 java导出word 动态填充数据
  • ¥20 扑克的算牌公式及软件制作
  • ¥20 如何通过云图中RPG去计算云图上不同位置的值?