NC21467. [NOIP2018]货币系统
描述
输入描述
输入的第一行包含一个整数T,表示数据组数。接下来按照如下格式分别给出T组数据。
每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。
输出描述
输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。
示例1
输入:
2 4 3 19 10 6 5 11 29 13 19 17
输出:
2 5
说明:
在第一组数据中，货币系统(2, [3,10])和给出的货币系统(n, a)等价，并可以验证不存在m < 2的等价的货币系统，因此答案为2。C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 496K, 提交时间: 2019-08-08 21:04:55
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int cases;
cin>>cases;
while(cases--){
int n,a[120],bp[25005]={1};
cin>>n;
int flag=n;
for(int j=0;j<n;j++){
cin>>a[j];
}
sort(a,a+n);
for(int k=0;k<n;k++){
if(bp[a[k]]){
flag--;
continue;
}
for(int t=a[k];t<=a[n-1];t++){
bp[t]|=bp[t-a[k]];
}
}
cout<<flag<<endl;
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 26ms, 内存消耗: 5260K, 提交时间: 2022-11-27 14:57:02
#include<bits/stdc++.h>
using namespace std;
int t,n,a[123],h[1234567];
int main(){
cin>>t;
while(t--){
cin>>n;
int ans=0;
memset(h,0,sizeof(h));
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);h[0]=1;
for(int i=1;i<=n;i++){
if(!h[a[i]])ans++;
for(int j=a[i];j<=a[n];j++)h[j]+=h[j-a[i]];
}cout<<ans<<endl;
}
}