学步园

思路：原以为可以用贪心解，但先付大钱，可能会无解（但其实是有解的） 用动态规划解 但你不知总钱数的范围 无法建数组
最后改用DFS深搜实现

//125MS   
204K
#include <stdio.h>
int coin[] = {1,2,5,10,20,50,100,200,500,1000};
int num[11];
int ans[11],flag;

void dfs (int pay,int p)
{
    if
(flag)   //当前以找到 返回
       
return ;
    if (p == -1)
//如果已经找完所有面值的钱&& 钱数为0 说明找到 flag ==
1
    {
       
if (pay == 0)
           
flag = 1;
       
return ;
    }
    int i,max =
pay/coin[p];
    if (max
>
num[p])    
//用该面值的钱最多能付多少 从多到少一张张的找
       
max = num[p];
    for (i =
max;i >= 0;i --)
    {
       
ans[p] = i;
       
dfs(pay-i*coin[p],p-1);
       
if (flag)
           
return ;
    }
}

int main ()
{
    int
i,count;
    while
(1)
    {
       
count = 0;
       
flag = 0;
       
for (i = 0; i < 11; i ++)
       
{
           
ans[i] = 0;
           
scanf ("%d",&num[i]);
           
if (num[i] == 0)
           
count ++;
       
}
       
if (count == 11)
       
break;
       
dfs (num[10],9);
       
if (flag)
       
{
           
int res = 0;