题目链接：?problemId=1954
Recently, Dearboy buys a dart for his dormitory, but neither Dearboy nor his roommate knows how to play it. So they decide to make a new rule in the dormitory, which goes as follows:
Given a numberN, the person whose scores accumulate exactly toNby the fewest times wins the game.
Notice once the scores accumulate to more thanN, one loses the game.
Now they want to know the fewest times to get the scoreN.
So the task is :Given all possible dart scores that a player can get one time andN, you are required to calculate the fewest times to get the exact scoreN.
Input
Standard input will contain multiple test cases. The first line of the input is a single integerT(1 <=T<= 50) which is the number of test cases. And it will be followed byTconsecutive test cases.
Each test case begins with two positive integersM(the number of all possible dart scores that a player can get one time) andN. Then the followingMintegers are the exact possible scores in the next line.
Notice:M(0 <M< 100),N(1 <N<= 1000000000), every possible score is (0, 100).
Output
For each test case, print out an integer representing the fewest times to get the exact scoreN.If the score can’t be reached, just print -1 in a line.
Sample Input
33 61 2 33 125 1 41 32
Sample Output
23-1Author:WANG, YijieSource:Zhejiang University Local Contest 2008
题意：
题yi：给定m，0<m<100，个数字w[],0<wi<100，求数字组合成 N (1 < N <= 1000000000) 的最小组合数，即：N = a1*w1 + a2*w2 + … + am*wm, 求 a1+a2+…+am的和最小分析：题目看上去就是一个完全背包问题，但因为 N 的数据量是10亿，因此肯定是计算用的而不能直接用于背包容量，因此需要优化。鸽巢定义应用：可以先将 w[] 排序，可以想到a1a1+a2a1+a2+a3…a1+a2+a3+…+a(n-1)(!!)（用%an去想，就是有an个鸽巢）这个东西，就是说如果 选用 小于an 的数字超过 an个 (m>an) (!!)，那就会出现某个子集是an的倍数，直接可以用an表示掉（第二次应用，要记住了）回到题目，所以对于最大的 w[i]，它能承受的子集和是 w[i]*w[i](这里有所放宽，但最大都为100*100，可以让dp接受，没有问题)，，所以就可以开一个10000的数组做dp了。
代码如下:
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define INF 0x3f3f3f3f#define maxn 10000int dp[maxn+147];int w[147];int M, N;int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&M,&N);for(int i = 1; i <= M; i++){scanf("%d",&w[i]);}sort(w+1, w+M+1);int cnt = 0;if(N > maxn)//鸽巢原理{int tt = (N-maxn)%w[M]+maxn;cnt = (N-tt)/w[M];N = tt;}memset(dp,INF,sizeof(dp));dp[0] = 0;for(int i = 1; i <= M; i++){for(int j = w[i]; j <= N; j++){dp[j] = min(dp[j],dp[j-w[i]]+1);}}if(dp[N] == INF){printf("-1\n");continue;}int ans = dp[N]+cnt;printf("%d\n",ans);}return 0;}
在时间里面我们什么也不能留下，包括痛苦，快乐和生命。
