本文主要是介绍Too Rich ICPC 2015 Changchun A dfs+思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
9255: Too Rich
时间限制: 1 Sec 内存限制: 128 MB
提交: 100 解决: 22
[提交] [状态] [讨论版] [命题人:admin]
题目描述
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.
输入
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 c i means how many coins/banknotes in denominations of i dollars in your wallet.
1≤T≤20000
0≤p≤109
0≤c i≤100000
输出
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‘.
样例输入
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
样例输出
9
-1
36
来源/分类
ICPC 2015 Changchun
[提交] [状态]
遗憾，比赛时想到了正确的解法，但是种种原因，最后没写。。。
题意：有十种面额的硬币的对应的个数，给一个钱数n，求恰好等于n且硬币个数最多的结果
开始直接写了贪心，然后发现贪不过去
样例在这里：250 1 0 0 3 1 0 1 0 0 0 答案是2，贪心是-1
190 0 0 0 5 100 0 0 0 0 0 答案是5，贪心应该还是-1
然后想了下dfs，但是细节不太会写
思路：算出所给的所有的钱数，减去要求的n，接着用这个减去的值m求硬币个数最少的情况，最后相减就可以
这个dfs好写一些，但是一直处在dfs能看懂但自己写不出来的状态。。。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50;
const int inf=0x3f3f3f3f;
ll num[20];
ll val[20]={0,1,5,10,20,50,100,200,500,1000,2000};
ll use[20];
ll ans;
void dfs(int x,ll sum,ll cnt){if(!sum){ans=min(ans,cnt);return ;}if(x<1) return ;use[x]=min(sum/val[x],num[x]);dfs(x-1,sum-val[x]*use[x],cnt+use[x]);if(use[x]>=1){use[x]--;dfs(x-1,sum-val[x]*use[x],cnt+use[x]);}
}
int main()
{int t;scanf("%d",&t);while(t--){memset(use,0,sizeof(use));ll p,sum=0;ll cnt=0;scanf("%lld",&p);for(int i=1; i<=10; i++){scanf("%lld",&num[i]);sum+=num[i]*val[i];cnt+=num[i];}sum-=p;if(sum<0){printf("-1\n");continue;}ans=inf;dfs(10,sum,0);if(ans==inf){printf("-1\n");}else printf("%lld\n",cnt-ans);}return 0;
}
这篇关于Too Rich ICPC 2015 Changchun A dfs+思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
