a[i] 表示第i个数是第i-1个数的多少倍 a[1]=1 那么第i个数 b[i]=∑ij=1a[j] 那么对于一个价格为n的物品第 i 个数用的次数nb[i]%a[i 1]。 所以我们可以考虑dp，f[i]表示最后一个数为，然后除了i以外前面的数的最小的硬币数量是多少.
#include<cstdio> #include<algorithm> #include<cstring> const int N = 100005; int f[N], n, a[51], ret; void G (int &num) { static char a; static bool fl; for (a = getchar (), fl = false; a > '9' || a < '0'; a = getchar ()) if (a == '-') fl = true; for (num = 0; a >= '0' && a <= '9'; a = getchar ()) num = (num << 3) + (num << 1) + a - '0'; if (fl) num = -num; } void Min (int &x, int y) { if (x > y) x = y; } int main () { // freopen ("3233.in", "r", stdin); int S = 0; G (n); for (int i = 1; i <= n; ++i) G (a[i]); std :: sort (a + 1, a + n + 1); S = a[n]; memset (f, 0x3f, sizeof f); f[1] = 0; for (int i = 1; i <= S; ++i) { for (int j = 2; i * j <= S; ++j) { ret = 0; int &tx = f[i * j]; for (int k = n; k; --k) { ret += a[k] / i % j; if (f[i] + ret > tx) break; } Min (tx, f[i] + ret); } } int ans = 0x3f3f3f3f; for (int i = 1; i <= S; ++i) { ret = 0; for (int k = 1; k <= n; ++k) ret += a[k] / i; f[i] += ret; if (ans > f[i]) ans = f[i]; } printf ("%d\n", ans); return 0; }