80pts求助#5#6WA

Eric_Shi @ 2024-01-17 20:41:16

by Norsuman371 @ 2024-01-17 21:26:58

@FYCCCTA

by Norsuman371 @ 2024-01-17 21:27:25

@2011FYCCCTA

by Eric_Shi @ 2024-01-17 21:31:21

@Norsuman371 冒昧吱一声：“啊？”

by Eric_Shi @ 2024-01-17 21:38:48

#include <iostream>
using namespace std;

#define MAXN 32001
int n, m, v, p, q;
int mw[MAXN], mv[MAXN]; //主件重量,价值
int fw[MAXN][3], fv[MAXN][3]; //主件对应的附件(最多2个)的重量,价值
int cnt[MAXN]; //每个主件的附件数量
int f[MAXN];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> v >> p >> q;
        if (q == 0) { //主件
            mw[i] = v;
            mv[i] = v*p;
        } else { //附件
            cnt[q]++;
            fw[q][cnt[q]] = v;
            fv[q][cnt[q]] = v*p;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = n; j >= mw[i]; j--) {
            f[i] = max(f[i], f[j-mw[i]]+mv[i]); //主件
            if (j >= mw[i] + fw[i][1])
                f[j] = max(f[j], f[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]); //主件+附件1
            if (j >= mw[i] + fw[i][2])
                f[j] = max(f[j], f[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]); //主件+附件2
            if (j >= mw[i] + fw[i][1] + fw[i][2])
                f[j] = max(f[j], 
                f[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]); //主件+附件1+附件2
        }
    }
    cout << f[n];

    return 0;
}

by Norsuman371 @ 2024-01-17 21:40:54

@EricTedd 不会呀，请神犇朋友解答（简洁表示：我太菜了）

by 2011FYCCCTA @ 2024-01-17 21:49:34

@EricTedd 其中一个错误： f[i] = max(f[i], f[j-mw[i]]+mv[i]); 改为 f[i] = max(f[j], f[j-mw[i]]+mv[i]);

by 2011FYCCCTA @ 2024-01-17 21:50:47

emm我犯傻了，前面的f[i]也要改

by 2011FYCCCTA @ 2024-01-17 21:51:15

AC了

by Eric_Shi @ 2024-01-17 21:57:42

@2011FYCCCTA 哦哦谢谢，我手残眼瞎脑子短路