題干：

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 number?N, the person whose scores accumulate exactly to?N?by the fewest times wins the game.

Notice once the scores accumulate to more than?N, one loses the game.

Now they want to know the fewest times to get the score?N.

So the task is :?
Given all possible dart scores that a player can get one time and?N, you are required to calculate the fewest times to get the exact score?N.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer?T?(1 <=?T?<= 50) which is the number of test cases. And it will be followed by?T?consecutive test cases.

Each test case begins with two positive integers?M(the number of all possible dart scores that a player can get one time) and?N. ?Then the following?M?integers 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 score?N.
If the score can't be reached, just print -1 in a line.

Sample Input

3 3 6 1 2 3 3 12 5 1 4 1 3 2

Sample Output

2 3 -1

題目大意：

? 給m(<=100)個(gè)數(shù)，每個(gè)數(shù)的范圍(1,100)，一個(gè)n(<=1e9)，問你能否通過組合這m個(gè)數(shù)來湊出n來。如果可以就輸出最小步數(shù)，反之輸出-1。

解題報(bào)告：

? n<=20000的時(shí)候可以直接背包，如果大于20000就先貪心最大的數(shù)，縮小下范圍到20000以內(nèi)，然后直接讀表。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 20000 + 5; const ll INF = 9999999999; ll dp[MAX]; int a[MAX]; int main() {int t;cin>>t;while(t--) {int m;ll n;scanf("%d%lld",&m,&n);for(int i = 0; i<MAX; i++) dp[i] = INF;for(int i = 1; i<=m; i++) scanf("%d",a+i);sort(a+1,a+m+1);dp[0] = 0;for(int i = 1; i<=m; i++) {for(int j = a[i]; j<=20000; j++) {dp[j] = min(dp[j],dp[j-a[i]] +1);}}ll qq = a[m];if(n<=20000) {if(dp[n] == INF) printf("-1\n");else printf("%lld\n",dp[n]);continue;}ll sub = (n-19000) / a[m];n -= sub * a[m];if(dp[n] == INF) printf("-1\n");else printf("%lld\n",sub + dp[n]);}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【ZOJ - 2955】Interesting Dart Game（背包，结论，裴蜀定理，数论）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。