本文共 2277 字，大约阅读时间需要 7 分钟。

题目：

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

 

 

33 61 2 33 125 1 41 32

 

 

Sample Output

 

 

23-1

思路：

因为n很大，有1e10,直接dp的话行不通，我们可以通过缩小dp范围来进行优化，当大于1e4时，可以减去尽量多的最大数来缩小到1e4，然后进行dp。

dp的话套用完全背包问题。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;const int maxn=1e4+5;const int INF=0x3f3f3f3f;int t;int n,m;int a[maxn];int dp[maxn<<1];int Max;int main(){    memset (a,0,sizeof(a));    scanf("%d",&t);    while(t--)    {        Max=-0x3f3f3f3f;        int ans=0;        scanf("%d%d",&m,&n);        for (int i=1;i<=m;i++)        {            scanf("%d",&a[i]);            Max=max(Max,a[i]);        }        if(n>10000)        {            int t=n-10000;            ans+=t/Max;            n=10000+t%Max;        }        for (int i=1;i<=n;i++) dp[i]=INF;        dp[0]=0;        for (int i=1;i<=m;i++)        {            for (int j=a[i];j<=n;j++)            {                dp[j]=min(dp[j-a[i]]+1,dp[j]);            }        }        if(dp[n]==INF) printf("-1\n");        else printf("%d\n",dp[n]+ans);    }    return 0;}
      
     
    
   

 

转载地址：http://skoen.baihongyu.com/