竞赛讨论区 > 【题解】第一次写题解,大佬轻喷。

【题解】第一次写题解,大佬轻喷。

头像
小明201810191840251
编辑于 2019-04-10 10:59:01 APP内打开
赞 5 | 收藏 0 | 回复2 | 浏览1257
/*
题目所说的等效也就是说在减少几个货币单位之后仍然可以凑出同样的货币值。
那么也就是说,某系货币单位可以用其他的货币单位代替。
并且一定是比它小的货币单位(废话)。那么也就是说我们可以先排序,然后从第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;
ll n,x,y;
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;
}

2条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐