题解【CJOJ1071/UVA】硬币问题

Description

有n种硬币，面值分别为v1, v2, ..., vn，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。

Input

第一行两个整数，n，S（1≤n≤100， 0≤S≤100000）。
第二行n个整数vi-1...n(1≤vi≤S)。

Output

第一行两个整数，分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。
第二行 a 个整数分别表示使用的是第几种硬币。
第三行 b 个整数分别表示使用的是第几种硬币。

Sample Input

6 12
1 2 3 4 5 6

Sample Output

2 12
6 6
1 1 1 1 1 1 1 1 1 1 1 1

Hint

样例是特殊的，编号和面值是相同的。你编写程序的时候要注意输出编号而不是面值。
结果按编号升序输出字典序小一种。

Source

入门经典，DP，DAG

Solution

考虑DP。

对于每个值i(1<=i<=s)，我们可以枚举j，使得i从i-v[j]增加一个v[j]得来。因此，我们有了下面的代码片段：

for(register int i=; i<=s; i++)

    {

        for(register int j=; j<=n; j++)

        {

            if(i-v[j]<)

            {

                continue;

            }

            else

            {

                if(mi[i]>mi[i-v[j]]+)

                {

                    mi[i]=mi[i-v[j]]+;

                    pi[i]=i-v[j];

                }

                if(mx[i]<mx[i-v[j]]+)

                {

                    mx[i]=mx[i-v[j]]+;

                    px[i]=i-v[j];

                }

            }

        }

    }

这样一来，题目就迎刃而解了！

Code

 #include <bits/stdc++.h>

 using namespace std;

 inline int read()

 {

     int f=,x=;

     char c=getchar();

     while(c<'' || c>'')

     {

         if(c=='-')f=-;

         c=getchar();

     }

     while(c>='' && c<='')

     {

         x=x*+c-'';

         c=getchar();

     }

     return f*x;

 }

 int s1,n,v[],s,a,b,ma,mb,d[],mi[],mx[],pi[],px[];

 int an[];

 int main()

 {

     n=read(),s=read();

     for(register int i=; i<=n; i++)

     {

         v[i]=read();

         d[v[i]]=i;

     }

     for(register int i=; i<=s; i++)

     {

         mi[i]=;//组成值i最少需要多少枚硬币

         mx[i]=-;//组成值i最多需要多少枚硬币

     }

     mi[]=;

     mx[]=;

     for(register int i=; i<=s; i++)

     {

         for(register int j=; j<=n; j++)

         {

             if(i-v[j]<)

             {

                 continue;

             }

             else

             {

                 if(mi[i]>mi[i-v[j]]+)

                 {

                     mi[i]=mi[i-v[j]]+;

                     pi[i]=i-v[j];

                 }

                 if(mx[i]<mx[i-v[j]]+)

                 {

                     mx[i]=mx[i-v[j]]+;

                     px[i]=i-v[j];

                 }

             }

         }

     }

     if(mi[s]== || mx[s]==-)//如果组成不了s

     {

         printf("-1");//输出无解

         return ;

     }

     printf("%d %d\n",mi[s],mx[s]);//输出最小组成数

 　　 //输出方案

     s1=s;

     int T=;

     memset(an,,sizeof(an));

     while(s1>)

     {

         an[++T]=d[s1-pi[s1]];

         s1=pi[s1];

     }

     sort(an+,an++T);

     for(register int i=; i<=T; i++)

     {

         printf("%d ",an[i]);

     }

     puts("");

     s1=s;

     T=;

     memset(an,,sizeof(an));

     while(s1>)

     {

         an[++T]=d[s1-px[s1]];

         s1=px[s1];

     }

     sort(an+,an++T);

     for(register int i=; i<=T; i++)

     {

         printf("%d ",an[i]);

     }

     return ;//结束

 }

巴特西