Piggy-Bank

朴素

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

const int N = 510;

const int M = 10010;

int f[N][M];
int n, m;
int w[N], v[N];

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        int E, F;
        cin >> E >> F;
        m = F - E;
        cin >> n;

        for (int i = 1; i <= n; i ++ )

            cin >> w[i] >> v[i];
        memset(f, 0x3f, sizeof f);

        for (int i = 0; i <= n; i ++ )

            f[i][0] = 0;

        for (int i = 1; i <= n; i ++ )

            for (int j = 0; j <= m; j ++ ) {

                f[i][j] = f[i - 1][j];

                if (j >= v[i])
                    f[i][j] = min(f[i][j], f[i][j - v[i]] + w[i]);
            }

        if (f[n][m] != INF)
            printf("The minimum amount of money in the piggy-bank is %d.\n", f[n][m]);
        else
            puts("This is impossible.");
    }

    return 0;
}

优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

const int N = 510;

const int M = 10010;

int f[M];
int n, m;
int w[N], v[N];

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        int E, F;
        cin >> E >> F;
        m = F - E;
        cin >> n;

        for (int i = 1; i <= n; i ++ )

            cin >> w[i] >> v[i];
        memset(f, 0x3f, sizeof f);
        f[0] = 0;

        for (int i = 1; i <= n; i ++ )

            for (int j = v[i]; j <= m; j ++ )

                f[j] = min(f[j], f[j - v[i]] + w[i]);


        if (f[m] != INF)
            printf("The minimum amount of money in the piggy-bank is %d.\n", f[m]);
        else
            puts("This is impossible.");
    }

    return 0;
}

CRB and His Birthday

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

const int M = 2010;

int n, m;
int v[N], a[N], b[N];
int f[M];

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        cin >> m >> n;

        for (int i = 1; i <= n; i ++ )

            cin >> v[i] >> a[i] >> b[i];

        memset(f, 0, sizeof f);

        for (int i = 1; i <= n; i ++ )

            for (int j = m; j >= v[i]; j -- )

                f[j] = max(f[j], f[j - v[i]] + a[i] + b[i]);  // 01背包

        for (int i = 1; i <= n; i ++ )

            for (int j = v[i]; j <= m; j ++ )

                f[j] = max(f[j], f[j - v[i]] + a[i]);  // 完全背包
        cout << f[m] << endl;
    }

    return 0;
}

超级楼梯

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50;

int f[N];
int w[] = {0, 1, 2};

int main() {
    f[1] = 1;
    f[2] = 1;

    for (int j = 3; j <= N; j ++ )

        f[j] = f[j - 1] + f[j - 2];

    int t;
    cin >> t;

    while (t -- ) {
        int n;
        cin >> n;
        cout << f[n] << endl;
    }
}