P1064 金明的预算方案

admin

https://www.luogu.org/problemnew/show/P1064

题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件           附件

电脑           打印机，扫描仪

书柜           图书

书桌           台灯，文具

工作椅        无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0个、 1 个或 2 个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1−5 表示，第 5等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 j 件物品的价格为 v[j] ，重要度为 w[j]，共选中了 k件物品，编号依次为 j1,j2,…,k则所求的总和为：

v[j1]*w[j1]+v[j2] *w[j2]+ …+v[jk] *w[jk]
请你帮助金明设计一个满足要求的购物单。

输入输出格式
输入格式：
第 1 行，为两个正整数，用一个空格隔开：

N N （其中 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 是所属主件的编号）

输出格式：
一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。

输入输出样例
输入样例#1：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出样例#1：
2200
说明
NOIP 2006 提高组 第二题

Scorpio

1. #include<iostream>
   
2. using namespace std;
   
3. int f[33600],mv[72],mp[72],av[72][3],ap[72][3];
   
4. int n,m,i,j,v,p,q;
   
5. int main()
   
6. {
   
7.     cin>>n>>m;
   
8.     for(i=1;i<=m;i++)
   
9.     {
   
10.         cin>>v>>p>>q;
    
11.         if(q==0)
    
12.         {
    
13.             mv[i]=v;
    
14.             mp[i]=p;
    
15.         }
    
16.         else
    
17.         {
    
18.             av[q][0]++;
    
19.             av[q][av[q][0]]=v;
    
20.             ap[q][av[q][0]]=p;
    
21.         }
    
22.     }
    
23.     for(i=1;i<=m;i++)
    
24.         for(j=n;mv[i]!=0&&j>=mv[i];j--)
    
25.         {
    
26.             f[j]=max(f[j-mv[i]]+mv[i]*mp[i],f[j]);
    
27.             if(j>=mv[i]+av[i][1])
    
28.                 f[j]=max(f[j-mv[i]-av[i][1]]+mv[i]*mp[i]+av[i][1]*ap[i][1],f[j]);
    
29.             if(j>=mv[i]+av[i][2])
    
30.                 f[j]=max(f[j-mv[i]-av[i][2]]+mv[i]*mp[i]+av[i][2]*ap[i][2],f[j]);
    
31.             if(j>=mv[i]+av[i][1]+av[i][2])
    
32.                 f[j]=max(f[j-mv[i]-av[i][1]-av[i][2]]+mv[i]*mp[i]+av[i][1]*ap[i][1]+av[i][2]*ap[i][2],f[j]);
    
33.         }
    
34.     cout<<f[n];
    
35.     return 0;
    
36. }
    

复制代码

zhwang

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int c[151][5],v[151][5],q[151];
   
5. int n,m;
   
6. int biao[151];
   
7. int flag;
   
8. int f[32001];
   
9. int best;
   
10. int main()
    
11. {
    
12.     scanf("%d%d",&n,&m);
    
13.     for(int i=1;i<=m;i++)
    
14.     {
    
15.         scanf("%d%d%d",&c[i][1],&v[i][1],&q[i]);
    
16.         v[i][1]=c[i][1]*v[i][1];
    
17.     }
    
18.     for(int i=1;i<=150;i++)
    
19.     {
    
20.         biao[i]=1;
    
21.     }
    
22.     for(int i=1;i<=m;i++)
    
23.     {
    
24.         if(q[i]>0)
    
25.         {
    
26.             for(int t=1;t<=m;t++)
    
27.             {
    
28.                 if(q[i]==t)
    
29.                 {
    
30.                     flag=t;
    
31.                     break;
    
32.                 }
    
33.             }
    
34.             biao[flag]++;
    
35.             c[flag][biao[flag]]=c[flag][1]+c[i][1];
    
36.             v[flag][biao[flag]]=v[flag][1]+v[i][1];
    
37.             if(biao[flag]==3)
    
38.             {
    
39.                 biao[flag]++;
    
40.                 c[flag][4]=c[flag][2]+c[i][1];
    
41.                 v[flag][4]=v[flag][2]+v[i][1];
    
42.             }
    
43.             c[i][1]=0;
    
44.             v[i][1]=0;
    
45.             q[i]=0;
    
46.         }
    
47.     }
    
48.     for(int i=1;i<=m;i++)
    
49.     {
    
50.         for(int j=n;j>=1;j--)
    
51.         {
    
52.             for(int k=1;k<=biao[i];k++)
    
53.             {
    
54.                 if(j<c[i][k])
    
55.                 {
    
56.                     continue;
    
57.                 }
    
58.                 f[j]=max(f[j],f[j-c[i][k]]+v[i][k]);
    
59.             }
    
60.         }
    
61.     }
    
62.     for(int i=1;i<=32001;i++)
    
63.     {
    
64.         //printf("%d ",f[i]);
    
65.         if(f[i]>best)
    
66.         {
    
67.             best=f[i];
    
68.         }
    
69.     }
    
70.     printf("%d",best);
    
71.     return 0;
    
72. }

复制代码

walk_alone

1. #include <cstdio>
   
2. int max(int a,int b)
   
3. {
   
4.         if(a>b)
   
5.                 return a;
   
6.         else
   
7.                 return b;
   
8. }
   
9. int v[61],p[61],q[61],w[61],prev[61][3],prew[61][3];
   
10. int f[32001];
    
11. int main()
    
12. {
    
13.         int n,m;
    
14.         scanf("%d%d",&n,&m);
    
15.         for(int i=1;i<=m;i++)
    
16.         {
    
17.                 scanf("%d%d%d",&v[i],&p[i],&q[i]);
    
18.                 if(q[i]==0)
    
19.                         w[i]=p[i]*v[i];
    
20.                 else
    
21.                 {
    
22.                         prew[q[i]][0]++;
    
23.                         prev[q[i]][prew[q[i]][0]]=v[i];
    
24.                         prew[q[i]][prew[q[i]][0]]=v[i]*p[i];
    
25.                 }
    
26.         }
    
27.         for(int i=1;i<=m;i++)
    
28.                 for(int j=n;v[i]!=0 && j>=v[i];j--)
    
29.                 {
    
30.                         f[j]=max(f[j],f[j-v[i]]+w[i]);
    
31.                         if(j>=v[i]+prev[i][1])
    
32.                                 f[j]=max(f[j],f[j-v[i]-prev[i][1]]+w[i]+prew[i][1]);
    
33.                         if(j>=v[i]+prev[i][2])
    
34.                                 f[j]=max(f[j],f[j-v[i]-prev[i][2]]+w[i]+prew[i][2]);
    
35.                         if(j>=v[i]+prev[i][1]+prev[i][2])
    
36.                                 f[j]=max(f[j],f[j-v[i]-prev[i][1]-prev[i][2]]+w[i]+prew[i][1]+prew[i][2]);
    
37.                 }
    
38.         printf("%d",f[n]);
    
39.         return 0;
    
40. }

复制代码

吴语林

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <set>
   
7. using namespace std;
   
8. int main()
   
9. {
   
10.     int f[30005]={0},v[70]={0},fu[70][4]={0},w[70]={0},i,w_all,n;
    
11.     scanf("%d %d",&w_all,&n);
    
12.     w_all=w_all/10;
    
13.     for(i=1;i<=n;i++)
    
14.     {
    
15.         int q,w2;
    
16.         scanf("%d %d %d",&w[i],&q,&w2);
    
17.         w[i]=w[i]/10;
    
18.         v[i]=q*w[i];
    
19.         if(w2>0)
    
20.         {
    
21.             fu[w2][3]++;
    
22.             fu[w2][fu[w2][3]]=i;
    
23.             fu[i][0]=-1;
    
24.         }
    
25.     }
    
26.     for(i=1;i<=n;i++)
    
27.     {
    
28.         if(fu[i][0]==-1) continue;
    
29.         for(int j=w_all;j>=w[i];j--)
    
30.         {
    
31.             f[j]=max(f[j],f[j-w[i]]+v[i]);
    
32.             if(fu[i][3]==1)
    
33.             {
    
34.                 if(j-w[i]-w[fu[i][1]]>=0)
    
35.                     f[j]=max(f[j],f[j-w[i]-w[fu[i][1]]]+v[i]+v[fu[i][1]]);
    
36.                
    
37.             }
    
38.             if(fu[i][3]==2)
    
39.             {
    
40.                 if(j-w[i]-w[fu[i][1]]>=0)
    
41.                     f[j]=max(f[i],f[j-w[i]-w[fu[i][1]]]+v[i]+v[fu[i][1]]);
    
42.                 if(j-w[i]-w[fu[i][2]]>=0)
    
43.                     f[j]=max(f[j],f[j-w[i]-w[fu[i][2]]]+v[i]+v[fu[i][2]]);
    
44.                 if(j-w[i]-w[fu[i][1]]-w[fu[i][2]]>=0)
    
45.                     f[j]=max(f[j],f[j-w[i]-w[fu[i][2]]-w[fu[i][1]]]+v[fu[i][2]]+v[i]+v[fu[i][1]]);
    
46.             }
    
47.         }
    
48.     }
    
49.     printf("%d",f[w_all]*10);
    
50.     return 0;
    
51. }

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,num;
   
4. int v[65][3],p[65][3],f[3210],map[65];
   
5. int main()
   
6. {
   
7.     cin>>n>>m;
   
8.     n/=10;
   
9.     for(int i=1; i<=m; i++)
   
10.     {
    
11.         int v1,p1,f1;
    
12.         cin>>v1>>p1>>f1;
    
13.         v1/=10;
    
14.         if(!f1)
    
15.         {
    
16.             v[++num][0]=v1;
    
17.             p[num][0]=p1;
    
18.             map[i]=num;
    
19.         }
    
20.         else
    
21.         {
    
22.             f1=map[f1];
    
23.             if(!v[f1][1])
    
24.             {
    
25.                 v[f1][1]=v1;
    
26.                 p[f1][1]=p1;
    
27.             }
    
28.             else
    
29.             {
    
30.                 v[f1][2]=v1;
    
31.                 p[f1][2]=p1;
    
32.             }
    
33.         }
    
34. 
    
35.     }
    
36.     for(int i=1; i<=num; i++)
    
37.     {
    
38.         for(int j=n; j>=0; j--)
    
39.         {
    
40.             if(j>=v[i][0])
    
41.                 f[j]=max(f[j],f[j-v[i][0]]+v[i][0]*p[i][0]);
    
42.             if(j>=v[i][0]+v[i][1])
    
43.                 f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]);
    
44.             if(j>=v[i][0]+v[i][2])
    
45.                 f[j]=max(f[j],f[j-v[i][0]-v[i][2]]+v[i][0]*p[i][0]+v[i][2]*p[i][2]);
    
46.             if(j>=v[i][0]+v[i][1]+v[i][2])
    
47.                 f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]+v[i][2]*p[i][2]);
    
48.         }
    
49.      //   cout<<f[n]*10<<endl;
    
50.     }
    
51.     cout<<f[n]*10<<endl;
    
52.     return 0;
    
53. }
    

复制代码

type尧

1. //
   
2. #include<bits/stdc++.h>
   
3. #define maxm 70
   
4. #define maxn 32005
   
5. using namespace std;
   
6. int n,m;
   
7. int main_item_price[maxm];                                                                        //主件
   
8. int main_item_value[maxm];
   
9. int item_attached_main_price[maxm][3];                                                //附件
   
10. int item_attached_main_value[maxm][3];
    
11. int f[maxn];                                                                                                //状态
    
12. void getdata()
    
13. {
    
14.         int main_or_attached,price,value;
    
15.         cin>>n>>m;
    
16.         for(int i=1;i<=m;i++){
    
17.                 cin>>price>>value>>main_or_attached;
    
18.                 if(!main_or_attached){
    
19.                         main_item_price[i]=price;                                                        //这代码可读性太差了
    
20.                         main_item_value[i]=price*value;
    
21.                 }
    
22.                 else{
    
23.                         item_attached_main_price[main_or_attached][0]++;
    
24.                         item_attached_main_price[main_or_attached][item_attached_main_price[main_or_attached][0]]=price;
    
25.                         item_attached_main_value[main_or_attached][item_attached_main_price[main_or_attached][0]]=price*value;
    
26.                 }
    
27.         }
    
28.         return;
    
29. }
    
30. void dp()
    
31. {
    
32.         for(int i=1;i<=m;i++)
    
33.                 for(int j=n;main_item_price[i]!=0&&j>=main_item_price[i];j--){
    
34.                         f[j]=max(f[j],f[j-main_item_price[i]]+main_item_value[i]);
    
35.                         if(j>=main_item_price[i]+item_attached_main_price[i][1])
    
36.                                 f[j]=max(f[j],f[j-main_item_price[i]-item_attached_main_price[i][1]]+main_item_value[i]+item_attached_main_value[i][1]);
    
37.                         if(j>=main_item_price[i]+item_attached_main_price[i][2])
    
38.                                 f[j]=max(f[j],f[j-main_item_price[i]-item_attached_main_price[i][2]]+main_item_value[i]+item_attached_main_value[i][2]);
    
39.                         if(j>=main_item_price[i]+item_attached_main_price[i][1]+item_attached_main_price[i][2])
    
40.                                 f[j]=max(f[j],f[j-main_item_price[i]-item_attached_main_price[i][1]-item_attached_main_price[i][2]]+main_item_value[i]+item_attached_main_value[i][1]+item_attached_main_value[i][2]);
    
41.                 }
    
42.         return;
    
43. }
    
44. void print()
    
45. {
    
46.         cout<<f[n];
    
47.         return;
    
48. }
    
49. int main()
    
50. {
    
51.         getdata();
    
52.         dp();
    
53.         print();
    
54.         return 0;       
    
55. }
    

复制代码