题目1395：爱钱的胡老板

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：601

解决：152

题目描述：

胡老板，别名浩帆，是九度技术组中最喜欢钱的一个，当然了，他钱肯定是没多少的，但是他唯一的乐趣也就是把玩手中不多的钱了。

胡老板难得出了趟国（当然了，也就越南老挝东南亚了，前面说了，他钱不多）。

在A国，他发现了一台自动兑换货币的机器。这时，他爱钱的兴趣又体现出来了，他想通过兑换一定数量的钱，来保证换取这个国家的所有种类的硬币。但是，这种自动兑换机的兑换策略并不知道，所以胡老板想让你帮忙计算下，是否存在这么一种可能，通过兑换一定数量的纸币，能够保证一定获取所有可能的硬币，假如存在，则只需要告诉胡老板其最小值；假如不存在，就输出-1。

例如，A国有2、5这两种面额的硬币，那么我们只需要兑换7面额的纸币即可保证获取2和5这两种面额的硬币；同样，若B国有1、2这两种面额的硬币，那我们就无能为力了，因为所有的面额，可能都是由面额为1的硬币组成。

 

输入：

每个测试案例包括两行：

第一行为整数N，代表硬币的种类，其中1 <= N <= 50。

第二行为N个大于0小于等于10000的整数，代表硬币的面额。注意，不同种类的硬币，面额也可能一样。

 

输出：

 

 

 

对于每个测试案例，输出一行：

若方案存在，则输出一个最小的值；若不存在，则输出-1。

 

 

 

样例输入：

22 521 221 1

样例输出：

7-1-1

答疑：

解题遇到问题?分享解题心得?讨论本题请访问：

只要他们的和能被所有金额一切表示且不能被一种金额单独表示

#include
         
          #include
          
           #include
           
            using namespace std;int w[51];int dp[10000*50+1];int n, sum;int main() {     while(cin >> n){         memset(dp,0,sizeof(dp));        memset(w,0,sizeof(w));        sum = 0;        for(int i=0;i
            
             > w[i];            sum += w[i];        }            dp[0] = 1;        for(int i=0;i
             
               1){
       //所求金额只能被多种金额一起表示，不能被一种金额单独表示                     break;                }            }        }        if(dp[sum] == 1){            cout << sum << endl;        }        else cout << "-1" << endl;    }    return 0;}