请大牛们看一下我的思路或代码细节哪里出问题了,谢谢 从第五个数据点之后都是wa

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

kguniverse @ 2020-02-22 14:52:24

我的思路是先将所有的主件的编号放在一个一维数组里,然后把所有主件所对应的附件放在一个二维数组里,然后进行01背包的想法,状态转移方程的对象是主件。然后如果选择了主件的话,将状态转移方程换成附件,然后进行01背包思路。最后找出花费钱数小于n最大值。

谢谢

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
#define maxm 65
#define maxn 32001

int v[maxm], w[maxm], q[maxm], dp[maxm][maxn], fujian[maxm][maxm], cnt[maxm], zhujian[maxm];

int max1 (int a, int b, int c) {
    if (a < b) a = b;
    if (a < c) a = c;
    return a;
}
int main() {
    int n, m;
    cin >> n >> m;
    int cnt1 = 1;
    for (int i = 1; i <= m; i++) {
        cin >> v[i] >> w[i] >> q[i];
        if (q[i]) fujian[q[i]][cnt[q[i]]++] = i;
        else zhujian[cnt1++] = i;
    }
    int i;
    for (i = 1; zhujian[i]; i++) {
        for (int t = 0; t <= n; t++) {
            if (t < v[zhujian[i]]) {
                dp[zhujian[i]][t] = dp[zhujian[i - 1]][t];
                continue;
                }
            else dp[zhujian[i]][t] = max1(dp[zhujian[i]][t], dp[zhujian[i - 1]][t], dp[zhujian[i - 1]][t - v[zhujian[i]]] + v[zhujian[i]] * w[zhujian[i]]);
            if (dp[zhujian[i]][t] == dp[zhujian[i - 1]][t - v[zhujian[i]]] + v[zhujian[i]] * w[zhujian[i]]) { //当选择了主件时,状态转移方程的对象变为附件
                for (int j = 0; fujian[zhujian[i]][j]; j++) {
                    for (int r = 0; r <= n - v[zhujian[i]]; r++) {
                        if (r < v[fujian[zhujian[i]][j]]) continue;
                        dp[zhujian[i]][r + v[zhujian[i]]] = max(dp[zhujian[i]][r + v[zhujian[i]]], dp[zhujian[i]][r + v[zhujian[i]] - v[fujian[zhujian[i]][j]]]);
                    }
                }
            }
        }
    }

    int res = 0;
    for (int r = 0; r <= n; r++) {
        if (res < dp[zhujian[i - 1]][r]) res = dp[zhujian[i - 1]][r];
    }
    cout << res;
}

谢谢大佬可以帮忙


by LinkCutTree @ 2020-02-22 15:01:22

顺便问一句,这题的正解是不是树形背包?


by cmll02 @ 2020-02-22 15:01:46

BUSHI


by kguniverse @ 2020-02-22 16:54:11

刚刚看了答案感觉我的思路和他差不多,但是答案用的是结构体实现的,实在没找出来我的代码问题出在哪里惹。。


|