change money
1234567891011121314151617181920212223242526272829
#include <stdio.h>
#include <string.h>
#define inf 0x23333333
#define N 100005
int n, s, r; // n 种面值, 目标 s, 剩下 r 元找不开
int v[N]; // 面值
int dp[N]; // 记忆 d(s)
int d(int s) {
if (s < 0) return inf;
if (dp[s] != inf) return dp[s];
if (r > s) r = s;
int result = inf;
for (int i = 0; i < n; ++i)
if (result > d(s - v[i]) + 1)
result = d(s - v[i]) + 1;
if (result != inf) dp[s] = result;
return result;
}
int main() {
scanf("%d%d", &n, &s);
for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
dp[0] = 0; for (int i = 1; i <= s; ++i) dp[i] = inf; r = inf;
if (d(s) == inf) printf("%d\n", d(s - r));
else printf("%d\n", d(s));
}
C
INFO