acwing 532 货币系统
发布时间
阅读量：
阅读量
题面
题解
- 若两个货币系统等价，则存在以下性质
Property 1: The variables a₁ to aₙ can all be represented.
Property 2: In the optimal solution, the selected variables b₁ to bₘ must be chosen from the original variable set a₁ to aₙ.
Property 3: The selected variables b₁ to bₘ cannot be mutually represented by each other.
- 我们将a数组从小到大排序
(1) 如果一个数能由a₀至a_{i−1}表示，则该数必定不在b数组里
(2) 如果一个数无法由a₀到a_{i−1}表示，则该数必定存在于b数组里
- 我们检查任意数量的a₀到a_{i-1}是否能够表示a_i。如果可以，则这个问题就转化为求解完全背包问题下的方案总数。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 25010;
int t, n;
int a[N];
int f[M];
int main() {
cin >> t;
while (t--) {
memset(f, 0, sizeof f);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
int m = a[n];
int res = 0;
f[0] = 1;
for (int i = 1; i <= n; i++) {
if (!f[a[i]]) res++;
for (int j = a[i]; j <= m; j++) {
f[j] += f[j - a[i]];
}
}
cout << res << endl;
}
return 0;
}
AI写代码全部评论 (0)
还没有任何评论哟~