7.17 第4题 传送门：题目详情 - 货币系统 - JMYSOJ (jmfes.com) #include<bits/stdc++.h> using namespace std;

int dp[25010]; int a[110];

int main() { freopen("money.in","r",stdin); freopen("money.out","w",stdout); int T; cin >> T; for(int t = 1; t <= T; t ++){ memset(dp, 0, sizeof(dp)); memset(a, 0, sizeof(a)); dp[0] = 1; int n; cin >> n; for(int j = 1; j <= n; j ++){ cin >> a[j]; //使用 j 作为索引读取数据 } sort(a + 1, a + n + 1); int max_a = a[n]; int ans = 0; for(int j = 1; j <= n; j ++){ if(dp[a[j]] > 0) continue; // 如果当前面额已能被更小面额表示，则跳过 else ans ++; // 否则加入基货币集 for(int k = a[j]; k <= max_a; k ++){ dp[k] |= dp[k - a[j]]; // 位运算，正确的状态转移：判断是否能表示 } } cout << ans << endl; } return 0; }