题目描述
状态定义:f(i,j) : 考虑前i个数,是否能凑出j。 boolean
状态计算:
首先肯定是按y总所说从大到小排序。
用完全背包做出。
然后判断 i-1 能否凑出 A【i】 这个价值,能答案–1。
样例
import java.io.*;
import java.util.Arrays;
public class 货币系统2 {
static int T;
static int N;
static int A[];
static boolean dp[][]; // 考虑前i个数,价格为j时。能否被前面的数表示出来。
public static void main(String[] args) throws IOException {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(cin.readLine().trim());
while(T-->0){
N = Integer.parseInt(cin.readLine().trim());
A = new int[N+1];
String s[] = cin.readLine().split("\\s+");
for(int i = 1;i<=N;i++){
A[i] = Integer.parseInt(s[i-1]);
}
//------------------------------------------
Arrays.sort(A,1,1+N); //排序
dp = new boolean[N+1][A[N]+1];
dp[0][0] = true;
for(int i = 1;i<=N;i++){ //初始化
dp[i][A[i]]=true;
}
//依次判断后面大的数能否被前面小的数表示出来
for(int i = 1;i<=N;i++){
for(int j = 1;j<=A[N];j++){
if(A[i]==j) continue;
//一个不选 能否被表示。
dp[i][j] = dp[i-1][j];
//选 选几个
if(j>=A[i]) dp[i][j] = dp[i][j] || dp[i][j-A[i]]; //直接优化。
}
}
int ans = N;
for(int i = 1;i<=N;i++){ //i-1就很灵性。
if(dp[i-1][A[i]]==true) ans--;
}
System.out.println(ans);
}
}
}