洛谷 金明的预算方案

题号:P1064
一维滚动数组优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int v[65],p[65],q[65],w[65];
int q1[65],q2[65];
int iptr;
int f[35000];
void insert_subgood(int main,int sub){
    if(q1[main]==0)q1[main]=sub;
    else q2[main]=sub;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        w[i]=v[i]*p[i];
        if(q[i]!=0){
            insert_subgood(q[i],i);
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]!=0)continue;
        for(int j=n;j>=0;j--){
            if(j-v[i]>=0)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            if(q1[i]!=0&&j-v[i]-v[q1[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]]+w[i]+w[q1[i]]);
            if(q2[i]!=0&&j-v[i]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q2[i]]]+w[i]+w[q2[i]]);
            if(q1[i]!=0&&q2[i]!=0&&j-v[i]-v[q1[i]]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]-v[q2[i]]]+w[i]+w[q1[i]]+w[q2[i]]);
        }
    }
    cout<<f[n];
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注