Bone Collector

朴素做法

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

using namespace std;

const int N = 1010;

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

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

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

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

            cin >> w[i];

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

            cin >> v[i];

        memset(f, 0, sizeof f);

        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] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }

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

    return 0;
}

优化

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

using namespace std;

const int N = 1010;

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

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

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

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

            cin >> w[i];

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

            cin >> v[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]] + w[i]);

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

    return 0;
}

Charm Bracelet

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

using namespace std;

const int N = 3410;

const int M = 12890;

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

int main() {
    int n, m;
    cin >> n >> m;

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

        cin >> w[i] >> v[i];


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

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

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

    cout << f[m] << endl;

    return 0;
}

饭卡

朴素做法

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

using namespace std;

const int N = 1010;

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

int main() {
    while (cin >> n && n) {
        for (int i = 1; i <= n; i ++ )

            cin >> w[i];
        cin >> m;
        sort(w + 1, w + 1 + n);
        int MAX = w[n];

        if (m < 5) {
            cout << m << endl;
            continue;
        }

        m -= 5;
        memset(f, 0, sizeof f);

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

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

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

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

        cout << m + 5 - MAX - f[n - 1][m] << endl;
    }

    return 0;
}

优化

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

using namespace std;

const int N = 1010;

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

int main() {
    while (cin >> n && n) {
        for (int i = 1; i <= n; i ++ )

            cin >> w[i];
        cin >> m;
        sort(w + 1, w + 1 + n);
        int MAX = w[n];

        if (m < 5) {
            cout << m << endl;
            continue;
        }

        m -= 5;
        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 << m + 5 - MAX - f[m] << endl;
    }

    return 0;
}

Big Event in HDU

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

using namespace std;

const int N = 5010;

int n;
int w[N];
int f[N * 50];

int main() {
    while (cin >> n) {
        if (n < 0)
            break;

        int sum = 0, cnt = 1;

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

            int v, m;
            cin >> v >> m;
            sum += v * m;

            while (m -- )
                w[cnt ++ ] = v;
        }

        memset(f, 0, sizeof f);

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

            for (int j = sum / 2; j >= w[i]; j -- )

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

        printf("%d %d\n", sum - f[sum / 2], f[sum / 2]);
    }

    return 0;
}