简单dp,小蒟蒻A不了

P1064 [NOIP2006 提高组] 金明的预算方案

Qing_fy @ 2021-07-26 20:47:56

qaq,我样例都没过,大佬求教```cpp

include <bits/stdc++.h>

using namespace std;

int a[65], b[65], pr[65], n, m; int c[65][2], d[32005];

int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int v, p, q; scanf("%d%d%d", &v, &p, &q); a[i] = v * p; pr[i] = v; if (!c[q][0]) c[q][0] = i; else c[q][1] = i; b[i] = q; } for (int i = 1; i <= m; i++) { int p = b[i], ls = c[p][0], rs = c[p][1]; for (int j = 0; j <= n; j++) { if (p) { if (pr[p] <= j) d[j] = max(d[j], d[j - pr[p]] + a[p]); if (ls && pr[p] + pr[ls] <= j) d[j] = max(d[j], d[j - pr[p] - pr[ls]] + a[p] + a[ls]); if (rs && pr[p] + pr[rs] <= j) d[j] = max(d[j], d[j - pr[p] - pr[rs]] + a[p] + a[rs]); if (ls && rs && pr[p] + pr[ls] + pr[rs] <= j) d[j] = max(d[j], d[j - pr[p] - pr[ls] - pr[rs]] + a[p] + a[ls] + a[rs]); } else if (pr[i] <= j) { d[j] = max(d[j], d[j - pr[i]] + a[i]); } } } printf("%d\n", d[n]); return 0; }


by Qing_fy @ 2021-07-26 20:48:09

#include <bits/stdc++.h>
using namespace std;

int a[65], b[65], pr[65], n, m;
int c[65][2], d[32005];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int v, p, q;
        scanf("%d%d%d", &v, &p, &q);
        a[i] = v * p;
        pr[i] = v;
        if (!c[q][0]) c[q][0] = i;
        else c[q][1] = i;
        b[i] = q;
    }
    for (int i = 1; i <= m; i++) {
        int p = b[i], ls = c[p][0], rs = c[p][1];
        for (int j = 0; j <= n; j++) {
            if (p) {
                if (pr[p] <= j) d[j] = max(d[j], d[j - pr[p]] + a[p]);
                if (ls && pr[p] + pr[ls] <= j) d[j] = max(d[j], d[j - pr[p] - pr[ls]] + a[p] + a[ls]);
                if (rs && pr[p] + pr[rs] <= j) d[j] = max(d[j], d[j - pr[p] - pr[rs]] + a[p] + a[rs]);
                if (ls && rs && pr[p] + pr[ls] + pr[rs] <= j) d[j] = max(d[j], d[j - pr[p] - pr[ls] - pr[rs]] + a[p] + a[ls] + a[rs]);
            } else if (pr[i] <= j) {
                d[j] = max(d[j], d[j - pr[i]] + a[i]);
            }
        }
    }
    printf("%d\n", d[n]);
    return 0;
}

by 0x3b800001 @ 2021-07-26 21:12:25

希丰展?使md


by baoziwu2 @ 2021-07-26 22:00:47

题目中应该理解为01背包,您是不是理解为完全背包了(


|