dp

1、Tyvj 1214 硬币问题

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <stack>#include <map>#include <set>#include <cmath>#include <cctype>#include <ctime>#include <cassert>using namespace std;#define REP(i, n) for (int i = 0; i < (n); ++i)#define eps 1e-9typedef long long ll;typedef pair<int, int> Pair;const int INF = 0x7fffffff;const int maxn = 110;int a[maxn], Max[10010], Min[10010];int n, s;int dfs_Max(int u);int dfs_Min(int u);int main() {#ifdef __AiR_H    freopen("in.txt", "r", stdin);#endif // __AiR_H    scanf("%d %d", &n, &s);    REP(i, n) { scanf("%d", &a[i]); }    sort(a, a + n);    memset(Max, -1, sizeof(Max)); Max[0] = 0; Min[0] = 0;    for (int i = 1; i <= s; ++i) { Min[i] = INF; }    dfs_Max(s); dfs_Min(s);    PRintf("%d/n", Min[s]);    printf("%d/n", Max[s]);#ifdef __AiR_H    printf("Time used = %.2fs/n", (double)clock() / CLOCKS_PER_SEC);#endif // __AiR_H    return 0;}int dfs_Max(int u) {    if (Max[u] < -1) { return -1; }    if (Max[u] >= 0) { return Max[u]; }    int max_t = -INF, t = 0;    REP(i, n) {        if (u < a[i]) { break; }        t = dfs_Max(u - a[i]);        if (t != -1) { max_t = max(max_t, 1 + t); }    }    return Max[u] = max_t;}int dfs_Min(int u) {    if (Min[u] < INF) { return Min[u]; }    int min_t = INF - 1, t = 0;    REP(i, n) {        if (u < a[i]) { break; }        t = dfs_Min(u - a[i]);        if (t < INF - 1) { min_t = min(min_t, 1 + t); }    }    return Min[u] = min_t;}
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <stack>#include <map>#include <set>#include <cmath>#include <cctype>#include <ctime>#include <cassert>using namespace std;#define REP(i, n) for (int i = 0; i < (n); ++i)#define eps 1e-9typedef long long ll;typedef pair<int, int> Pair;const int INF = 0x3f3f3f3f;const int maxn = 110;int a[maxn], Max[10010], Min[10010];int n, s;int main() {#ifdef __AiR_H    freopen("in.txt", "r", stdin);#endif // __AiR_H    scanf("%d %d", &n, &s);    REP(i, n) { scanf("%d", &a[i]); }    sort(a, a + n);    Max[0] = 0; Min[0] = 0;    for (int i = 1; i <= s; ++i) { Min[i] = INF; Max[i] = -INF; }    for (int i = 1; i <= s; ++i) {        REP(j, n) {            if (i < a[j]) { break; }            Min[i] = min(Min[i], Min[i - a[j]] + 1);            Max[i] = max(Max[i], Max[i - a[j]] + 1);        }    }    printf("%d/n", Min[s]);    printf("%d/n", Max[s]);#ifdef __AiR_H    printf("Time used = %.2fs/n", (double)clock() / CLOCKS_PER_SEC);#endif // __AiR_H    return 0;}