AcWing 532. 货币系统Java版
原题链接
中等
作者:
小赵想滑板
,
2024-01-23 15:12:19
,
所有人可见
,
阅读 45
Java 代码
import java.util.*;
public class Main{
public static void main(String[]args){
int N=110,M=25010;
int n;
int a[]=new int [N];
int f[]=new int[M];
Scanner sc=new Scanner(System.in);
int T;
T=sc.nextInt();
while(T>0){
T--;
n=sc.nextInt();
for(int i=0;i<n;i++) a[i]=sc.nextInt();
Arrays.sort(a, 0, n );
int m=a[n-1];
Arrays.fill(f, 0);
f[0] = 1;
int res=0;
for(int i=0;i<n;i++){
if(f[a[i]]==0) res++;
for(int j=a[i];j<=m;j++) f[j]+=f[j-a[i]];
}
System.out.println(res);
}
}
}