为什么只有60分?! ——蒟蒻求助

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

过_路_人 @ 2020-10-04 18:42:43

cpp
#include<bits/stdc++.h>
using namespace std;
int n, m;
int c[105][3], w[105][3], dp[32005];
int main(){
    cin >> n >> m;
    int cnt = 1;
    for (int i = 1; i <= m; i++) {
        int v, p, q;
        cin >> v >> p >> q;//v 价格, p 重要度, q 从属关系 
        if (!q) {
            c[cnt][0] = v;
            w[cnt][0] = v * p;
            cnt++;
        }
        else {
            if (c[q][1]){
                c[q][2] = v;
                w[q][2] = v * p;
            } 
            else {
                c[q][1] = v;
                w[q][1] = v * p;
            }
        }
    }
    cnt--;
    for (int i = 1; i <= cnt; i++) {
        for (int j = n; j >= 0; j--) {
            int temp = dp[j];
            if (j >= c[i][0]) {
                dp[j] = dp[j - c[i][0]] + w[i][0];
                for (int k = 1; k <= 2; k++) {
                    if (j - c[i][0] >= c[i][k])
                    dp[j] = max(dp[j - c[i][0] - c[i][k]] + w[i][k] + w[i][0], dp[j]);
                }
                if (j - c[i][0] - c[i][1] - c[i][2] >= 0) {
                    dp[j] = max(dp[j], dp[j - c[i][0] - c[i][1] - c[i][2]] + w[i][0] + w[i][1] + w[i][2]);
                }
            }
            dp[j] = max(dp[j], temp);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

by 圣嘉然 @ 2020-10-27 20:14:59

@过_路_人 emmm

if (!q) {
            c[cnt][0] = v;
            w[cnt][0] = v * p;
            cnt++;
        }
        else {
            if (c[q][1]){
                c[q][2] = v;
                w[q][2] = v * p;
            } 
            else {
                c[q][1] = v;
                w[q][1] = v * p;
            }

这里,主件和附件就对应不上了,大概是这样的:


by 圣嘉然 @ 2020-10-27 20:17:03

@过_路_人 可以这么搞

        if (!q) {
            c[i][0] = v;
            w[i][0] = v * p;
            gro[cnt++]=i;
        }

记录一下第cnt组的主件,遍历的时候

    for (int t = 1; t <= cnt; t++) {
        int i=gro[t];

后面就不用改了(因为还是i代替某一组的主件编号


by 智子 @ 2021-10-11 17:59:26

@圣嘉然 感谢


|