哪位大佬瞅瞅代码?

dengyuhy 2020-03-20 15:22:52 2020-03-20 15:37:11 33 返回题目

//饥民的欲死方案
#include <bits/stdc++.h>
using namespace std;
#define maxn 2010
#define maxf maxn

struct node {
    int w, q;
} v1[maxn], v2[maxn];

int n, m, f[maxf], w[maxn], q[maxn];

int main() {
    cin >> m >> n;
	m/=10;
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y >> z;
        x/=10;
        if (q[i]) {
            if (!v1[z].w) {
                v1[z].w = x;
                v1[z].q = v1[z].q*y;
            } else {
                v2[z].w = x;
                v2[z].q = v2[z].q*y;
            }
        } else {
            w[i] = x;
            q[i] = w[i]*y;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            f[j] = max(f[j], f[j - w[i]] + q[i]);
            if (j - w[i] - v1[i].w >= 0) {  //可选第一件
                f[j] = max(f[j], f[j - w[i] - v1[i].w] + q[i] + v1[i].w * v1[i].q);
            }
            if (j - w[i] - v2[i].w >= 0) {  //可选第二件
                f[j] = max(f[j], f[j - w[i] - v2[i].w ] + q[i] + v2[i].w * v2[i].q);
            	if (j - w[i] - v1[i].w - v2[i].w >= 0) {  //可选第二件 
                f[j] = max(f[j], f[j - w[i] - v1[i].w - v2[i].w] + q[i] + v1[i].w * v1[i].q + v2[i].w * v2[i].q);
            	}
            }
        }
    }
    for(int i=1;i<=n;i++){
    	f[0]=max(f[0],f[i]);
	}
    cout<<f[0]*10;
    return 0;
}

graph LR
a((状态转移方程))
in1[max:选,不选] --> pd1{如果可以选自己+附件1}
pd1 --> |可以| in2[max:选自己+附件,不选]
pd1 --> |不可以| pd2{如果可以选自己+附件2}
in2 --> pd2
pd2 --> |可以| in3[max:选自己+附件2,不选]
pd2 --> |不可以| pd3{如果可以选自己+附件1+附件2}
in3 --> pd3
pd3 --> |可以| in4[max:选自己+附件1+附件2,不选]

上面这段代码不要看,现在wikioi不支持markdown流程图,支持后再说吧

{{ vote && vote.total.up }}

共 1 条回复

cookiebus

金明的预算是一个分组背包, 还有的情况是两个都可以选,或者两个都不选