30分re求助大佬!

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

wozolu @ 2018-08-17 21:51:06

#include<cstdio>
#include<iostream> 
#include<cmath>
#include<memory.h>
using namespace std;
/*输入文件budget.in 的第1行,为两个正整数,用一个空格隔开:N m 
(其中N(<32000)表示总钱数,m(<60)为希望购买物品的个数。) 
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,
每行有3个非负整数 v p q(其中v表示该物品的价格(v<10000),
p表示该物品的重要度(1~5),q表示该物品是主件还是附件。
如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号)
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
*/
int v[100],p[100],q,d[100][100],pj[100],zj,f[100];
int main(){
    int n,m;
    cin>>n>>m;
    n/=10;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q;
        p[i]*=v[i];
        v[i]/=10;
        d[q][++d[q][0]]=i;
    }
    for(int i=1;i<=d[0][0];i++){
        int o=d[0][i];
        for(int j=n;j>=v[i];j--){
            f[j]=max(f[j-v[o]]+p[o],f[j]);
            if(j>v[d[o][1]]+v[o])f[j]=max(f[j-v[o]-v[d[o][1]]]+p[o]+p[d[o][1]],f[j]);
            if(j>v[d[o][2]]+v[o])f[j]=max(f[j-v[o]-v[d[o][2]]]+p[o]+p[d[o][2]],f[j]);
            if(j>v[d[o][1]]+v[d[o][2]]+v[o])f[j]=max(f[j-v[o]-v[d[o][2]]-v[d[o][1]]]+p[o]+p[d[o][1]]+p[d[o][2]],f[j]);
        }
    }
    cout<<f[n];
    return 0;
}

感觉自己打的和一个题解也没什么区别啊…


|