最大报销额

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

using namespace std;

const int N = 40;

const int M = 3e6 + 10;

int n;
char x;
double y, q;
double a, b, c;
int w[M];
int f[M];

int main() {
    while (cin >> q >> n) {
        q = q * 100;

        if (n == 0)
            break;
        int cnt = 1;

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

            bool flag = true;
            int m;
            cin >> m;
            a = b = c = 0;

            while (m -- ) {
                scanf(" %c:%lf", &x, &y);

                if (x == 'A')
                    a += y;
                else if (x == 'B')
                    b += y;
                else if (x == 'C')
                    c += y;
                else
                    flag = false;
            }

            if ((a + b + c) > 1000 || a > 600 || b > 600 || c > 600)
                flag = false;

            if (flag)
                w[cnt ++ ] = (a + b + c) * 100;
        }

        memset(f, 0, sizeof f);

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

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

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

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

            if (max < f[i])
                max = f[i];
        printf("%.2lf\n", max / 100.0);
    }

    return 0;
}

Robberies

朴素

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

using namespace std;

const int N = 110;

const int M = 10010;

double p;
int v[N];
double w[N];
int n;
double f[N][M]; // f[i][j]表示只看前i场排位赛且得到了j个积分的逃脱概率

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

    while (t -- ) {
        cin >> p >> n;
        int sum = 0;

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

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

        memset(f, 0, sizeof f);

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

            f[i][0] = 1.0; // 不摸鱼肯定逃脱

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

            for (int j = 0; j <= sum; 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]] * (1 - w[i]));
            }

        int ans = 0;

        for (int i = sum; i >= 0; i -- )

            if (f[n][i] > (1.0 - p)) {
                ans = i;
                break;
            }

        cout << ans << endl;
    }

    return 0;
}

优化

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

using namespace std;

const int N = 110;

const int M = 10010;

double p;
int v[N];
double w[N];
int n;
double f[M]; // f[i][j]表示只看前i场排位赛且得到了j个积分的逃脱概率

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

    while (t -- ) {
        cin >> p >> n;
        int sum = 0;

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

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

        memset(f, 0, sizeof f);

        f[0] = 1.0; // 不摸鱼肯定逃脱

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

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

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


        int ans = 0;

        for (int i = sum; i >= 0; i -- )

            if (f[i] > (1.0 - p)) {
                ans = i;
                break;
            }

        cout << ans << endl;
    }

    return 0;
}

CD

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

using namespace std;

const int N = 30;

const int M = 10010;

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

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

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

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

        // 01背包的路径保存
        int cnt = 1;
        int v = f[n][m];

        for (int i = n; i >= 1; i -- )

            if (f[i][v] == f[i - 1][v - w[i]] + w[i]) {
                v -= w[i];
                path[cnt ++ ] = w[i];
            }
        for (int i = cnt - 1; i >= 1; i -- )

            printf("%d ", path[i]);
        printf("sum:%d\n", f[n][m]);
    }

    return 0;
}