https://www.51goc.com/level/program/110/641

题目：

---

题目描述

奶牛王国现有货币系统的银币面值有1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000。

现在农夫打算在现有货币系统的基础上，再推出一种新面值：newBanknote。

有N头奶牛要购物，第i头奶牛购买的商品的价值是cost[i]。

现在你要回答N个问题，第i个问题是：至少需要多少枚银币才能恰好凑成cost[i]？

输入格式

输入文件名：641.in

第一行，两个整数：newBanknote和N。1 <= newBanknote <= 2000000000。 1<=N<=50。

第二行，N个整数，第i个整数是cost[i]。1 <= cost[i] <= 2000000000。

输出格式

输出文件名：641.out

共一行，N个整数，依次对应N个问题的答案。

输入/输出例子1

输入：

4700 4

53 9400 9401 30000

输出：

3 2 3 2

史山代码：

#include<bits/stdc++.h>
using namespace std;
int mintime=2000000005;
int pd[50005];
void thb(long long money,long long nowmoney,int times,long long newmoney){
	if(nowmoney==money){
		if(times<mintime){
			mintime=times;
		}
		return;
	}
	if(nowmoney>money) return;
	if(pd[1]<1) thb(money,nowmoney+1,times+1,newmoney);pd[1]++;
	if(pd[2]<5) thb(money,nowmoney+2,times+1,newmoney);pd[2]++;
	if(pd[5]<2) thb(money,nowmoney+5,times+1,newmoney);pd[5]++;
	if(pd[10]<2) thb(money,nowmoney+10,times+1,newmoney);pd[10]++;
	if(pd[20]<5) thb(money,nowmoney+20,times+1,newmoney);pd[20]++;
	if(pd[50]<2) thb(money,nowmoney+50,times+1,newmoney);pd[50]++;
	if(pd[100]<2) thb(money,nowmoney+100,times+1,newmoney);pd[100]++;
	if(pd[200]<5) thb(money,nowmoney+200,times+1,newmoney);pd[200]++;
	if(pd[500]<2) thb(money,nowmoney+500,times+1,newmoney);pd[500]++;
	if(pd[1000]<2) thb(money,nowmoney+1000,times+1,newmoney);pd[1000]++;
	if(pd[2000]<5) thb(money,nowmoney+2000,times+1,newmoney);pd[2000]++;
	if(pd[5000]<2) thb(money,nowmoney+5000,times+1,newmoney);pd[5000]++;
	if(pd[10000]<2) thb(money,nowmoney+10000,times+1,newmoney);pd[10000]++;
	if(pd[20000]<5) thb(money,nowmoney+20000,times+1,newmoney);pd[20000]++;
	if(pd[50000]<2) thb(money,nowmoney+50000,times+1,newmoney);pd[50000]++;
	thb(money,nowmoney+newmoney,times+1,newmoney);
}
int main(){
    int news,cow,cost;
    cin>>news>>cow;
    for(int i=1;i<=cow;i++){
    	cin>>cost;
    	thb(cost,0,0,news);
    	cout<<mintime<<" ";
    	mintime=2000000005;
    	for(int i=0;i<50005;i++){
    		pd[i]=0;
		}
	}
	return 0;
}

样例1，4错了，如53对应3却输出51

求调