【题解】第一次写题解，大佬轻喷。
/*
题目所说的等效也就是说在减少几个货币单位之后仍然可以凑出同样的货币值。
那么也就是说，某系货币单位可以用其他的货币单位代替。
并且一定是比它小的货币单位（废话）。那么也就是说我们可以先排序，然后从第k个货币单位开始测试是否可以用k-1之前的货币单位凑出一个a[k]。
核心代码 ：
dp[j]=dp[j-a[I]];
此处dp[j]表示凑一个j可以有多少种方法。
然后再判断是否dp[a[k]]为0就可以知道a[k]能否被代替，如果可以，则ans++;并且将其标记，因为它已经没有利用价值了。
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
ll n,x,y;
ll T;
int a[110];
int vis[110];
int dp[26000];
ll T;
int a[110];
int vis[110];
int dp[26000];
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
int ans=0;
memset(vis,0,sizeof(vis));
for(int k=1;k<n;k++){
dp[0]=1;
for(int i=0;i<k;i++){
if(vis[i])continue;
for(int j=a[i];j<=a[k];j++){
dp[j]+=dp[j-a[i]];
}
}
if(dp[a[k]]){
ans++;
vis[k]=1;
}
memset(dp,0,sizeof(dp));
}
printf("%d\n",n-ans);
}
return 0;
}
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
int ans=0;
memset(vis,0,sizeof(vis));
for(int k=1;k<n;k++){
dp[0]=1;
for(int i=0;i<k;i++){
if(vis[i])continue;
for(int j=a[i];j<=a[k];j++){
dp[j]+=dp[j-a[i]];
}
}
if(dp[a[k]]){
ans++;
vis[k]=1;
}
memset(dp,0,sizeof(dp));
}
printf("%d\n",n-ans);
}
return 0;
}
小天才公司福利 1341人发布