时间：2023-04-21 15:36:02 | 来源：网站运营
时间：2023-04-21 15:36:02 来源：网站运营
(DP) 代码源每日一题 Div1 货币系统：题目链接：Daimayuan Online Judge
在线咨询
int cal(int x) { int id = n; int cot = 0; while (x) { while (a[id] > x)id--; cot += x / a[id]; x -= x / a[id] * a[id]; } return cot;}最少货币数可以通过完全背包来获得，问题是背包的容量。int cal(int x) { int id = n; int cot = 0; while (x) { while (a[id] > x)id--; cot += x / a[id]; x -= x / a[id] * a[id]; } return cot;}void slove() { cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 0; i <= 20000; i++)f[i] = INF; f[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= 20000; j++) { f[j + a[i]] = min(f[j + a[i]], f[j] + 1); } } for (int i = 1; i <= 20000; i++) { if (f[i] != cal(i)) { NO; return; } } YES;}关键词：货币,系统
