【Luogu1064】金明的预算方案

Source and Judge

NOIP2006 提高组 T2
Luogu1064
Caioj1526

Problem

【Brief description】
如果要买归类为附件的物品,必须先买该附件所属的主件。
每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。
金明想买的东西很多,肯定会超过妈妈限定的N元。
于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。
他还从因特网上查到了每件物品的价格。
他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
【Input】
输入的第1行,为两个正整数,用一个空格隔开:N m (其中N表示总钱数,m为希望购买物品的个数。)
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,
每行有3个非负整数v p q
(其中v表示该物品的价格,p表示该物品的重要度(1~5),q表示该物品是主件还是附件。
如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号)
【Output】
输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)
【Limited conditions】
N<32000
m<60
v<10000
物品的价格都是10元的整数倍
【Sample input】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
【Sample output】
2200
【Sample explanation】

Record

30min

Analysis

请先思考后再展开

这题的关键在于附件的存在,但“附件的个数不超过2”大大降低了难度
那么对于每个主件,只有以下情况

  1. 只买主件
  2. 买主件和附件1
  3. 买主件和附件2
  4. 买主件和两个附件
    将输入整理后,就转化成了背包问题中的经典问题:采药

Code

请先思考后再展开
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//Zory-2018
//****************头文件****************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
ll mymax(ll x,ll y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
//****************全局常量****************
const int INF=0x3f3f3f3f;
//****************全局定义****************
int a[70][3],b[70][3];
int f[33000];
//****************实现****************
//****************主函数****************
int main()
{
int N,m;scanf("%d%d",&N,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
if(z==0) a[i][0]=x,b[i][0]=y;
else if(b[z][1]==0) a[z][1]=x,b[z][1]=y;
else a[z][2]=x,b[z][2]=y;
}
for(int i=1;i<=m;i++)
{
for(int j=N;j>=0;j--)
{
int x,y;
x=a[i][0];
y=a[i][0]*b[i][0];
if(j>=x) f[j]=mymax(f[j],f[j-x]+y);
x=a[i][0]+a[i][1];
y=a[i][0]*b[i][0]+a[i][1]*b[i][1];
if(j>=x) f[j]=mymax(f[j],f[j-x]+y);
x=a[i][0]+a[i][2];
y=a[i][0]*b[i][0]+a[i][2]*b[i][2];
if(j>=x) f[j]=mymax(f[j],f[j-x]+y);
x=a[i][0]+a[i][1]+a[i][2];
y=a[i][0]*b[i][0]+a[i][1]*b[i][1]+a[i][2]*b[i][2];
if(j>=x) f[j]=mymax(f[j],f[j-x]+y);
}
}
printf("%d",f[N]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8231.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%