本题就是一个贪心+完全背包，很容易想到如果想要用化简会被其他货币凑出的货币，那么就必须从小到大凑（因为大的一定凑不出小的，而小的有可能凑出大的）。所以由此如何判断呢？就写一个完全背包判断（而且不用每新的货币就重新计算，可以从前往后依次计算（减小时间复杂度））。这样判断后若无法凑出就ans++。（好了上代码！）
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<string> 5 #include<cstring> 6 using namespace std; 7 int T; 8 int num[109]; 9 int n,ans;//ans记录答案 10 bool dp[25009];//记录在某货币之前的所有货币可能凑出的值（false为不能，true为能） 11 int maxn;//记录整个货币系统中最大的面值 12 bool judge(int m)//判断num[m]是否已经凑出并计算加上这个面值之后可以凑出的值 13 { 14 if(dp[num[m]]==true)return true;//已经凑出了就返回true 15 dp[num[m]]=true;//那么就需要将其标记为true 16 for(int j=num[m];j<=maxn;j++)//完全背包模板但是已经知道了这个数是多少就不用去枚举了 17 { 18 if(dp[j-num[m]]==true)dp[j]=true; 19 } 20 return false;//直接返回false 21 } 22 void shaishu() 23 { 24 for(int i=1;i<=n;i++) 25 { 26 if(judge(i)==true)continue;//如果是可以被凑出ans就不用增加 27 else ans++; 28 } 29 } 30 int main() 31 { 32 cin>>T; 33 while(T--) 34 { 35 memset(num,0,sizeof(num)); 36 memset(dp,false,sizeof(dp));//一定要清空dp不然上几组数据的值都会残留在其中使答案不对 37 ans=0;//同时将ans归零 38 cin>>n; 39 for(int i=1;i<=n;i++)cin>>num[i],maxn=max(maxn,num[i]);//在读入的同时计算出最大的面值 40 sort(num+1,num+n+1);//排序将小面值放在前面 41 shaishu();//开始筛选 42 cout<<ans<<endl;//最后输出结果 43 } 44 }
