Bookshelf 2

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

using namespace std;

const int N = 30;

const int M = 2e7 + 10;

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

int main() {
    int b;
    int sum = 0;
    cin >> n >> b;

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

        cin >> w[i];
        sum += w[i];
    }

    m = sum;

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

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

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

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

        if (f[i] >= b) {
            cout << f[i] - b << endl;
            break;
        }

    return 0;
}

A Mini Locomotive

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

using namespace std;

const int N = 50010;

int n, m;
int w[N], sum[N];
int f[N][10];  // f[i][j] 表示只看前i个物品，使用的机车数量不超过j的选法的最大值

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

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

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

            cin >> w[i];
        cin >> m;

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

            sum[i] = sum[i - 1] + w[i];
        int res = sum[m];

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

            res += w[i];
            res -= w[i - m];
            sum[i] = res;
        }

        memset(f, 0, sizeof f);

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

            for (int j = 1; j <= 3; j ++ ) {

                f[i][j] = f[i - 1][j];
                f[i][j] = max(f[i][j], f[i - m][j - 1] + sum[i]);
            }

        cout << f[n][3] << endl;
    }

    return 0;
}

Investment

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

using namespace std;

const int N = 20;

const int M = 1e5 + 10;

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

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

    while (t -- ) {
        int year, pos;
        cin >> pos >> year;
        cin >> n;

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

            cin >> v[i] >> w[i];
            v[i] /= 1000;
        }

        while (year -- ) {
            int m = pos / 1000;
            memset(f, 0, sizeof f);

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

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

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

            pos += f[m];
        }

        cout << pos << endl;
    }

    return 0;
}

Cash Machine

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

using namespace std;

const int N = 110;

const int M = 1e5 + 10;

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

int main() {
    while (cin >> m >> n) {
        int cnt = 0;

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

            int k = 1;
            int s, W;
            cin >> s >> W;

            while (k <= s) {
                cnt ++ ;
                w[cnt] = k * W;
                s -= k;
                k *= 2;
            }

            if (s) {
                cnt ++ ;
                w[cnt] = s * W;
            }
        }

        if (n == 0 || m == 0) {
            puts("0");
            continue;
        }

        n = cnt;
        memset(f, 0, sizeof f);

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

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

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


        cout << f[m] << endl;
    }

    return 0;
}