C古韵之刺绣【noip模拟赛1】

发表于 | 分类于 ， | 阅读量 次

描述

日暮堂前花蕊娇，

争拈小笔上床描，

绣成安向春园里，

引得黄莺下柳条。

——胡令能《咏绣障》

古时女子四德中有一项——女红。女红的精巧程度对于女子来说是十分重要的。韵哲君十分爱好女红，尤其是刺绣。

当衬衣公司的Immortal掌柜在知道韵哲君有这一手艺后，交给韵哲君一个任务：在他所提供的各种各样大小的布上绣上精美的花纹（每匹布上只能绣一种花纹）。有3种花纹可以供韵哲君选择，每一体积布上的每种花纹的美观度c和所占体积v都不同。Immortal带了一个不知道是否足够装下所有刺绣作品的包，请你帮忙计算一下，Immortal的包里所能装下作品的最大美观度。

输入

第一行为两个数n（布的匹数，0<n<=100）、m（包的容积，0<m<=8000）；

第二行到第四行，每行有3个数据：花纹种类编号z（0<z<maxint）、每一体积布上这种花纹的美观度c[z]（0<c[z]<maxint）和每一体积布上绣的这种花纹的体积v[z]（0<z<maxint）；

第五行到n+4行每行有2个数据，分别是第i匹布的体积b[i]（0<b[i]< maxint）和这匹布上所绣花纹的种类编号z[i]。

输出

输出一个正整数，为Immortal的包里所能装下作品的最大美观度。

输入样例 1

5 100
8 2001 5
4 9 8
3 74 4
111 4
79 8
6 3
5 8
23 4

输出样例 1

10449

来源：
来自 <http://www.dingbacode.com/contest/19/problem/C>

题解：
01背包，注意布也有体积

代码：

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
#include <bits/stdc++.h>
using namespace std;

typedef  struct node{
int c;
int v;
}Node;

int B[105],Z[105];
int dp[8005];

map<int,Node> coke;

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=3;i++)
    {
        int c,v,z;
        cin>>z>>c>>v;
        coke[z].c=c;
        coke[z].v=v;
    }

    for(int i=1;i<=n;i++)
        cin>>B[i]>>Z[i];

    for(int i=1;i<=n;i++)
        for(int j=m;j>=B[i]*coke[Z[i]].v+B[i];j--)
        dp[j]=max(dp[j],dp[j-B[i]*coke[Z[i]].v-B[i]]+B[i]*coke[Z[i]].c);

    cout<<dp[m]<<endl;

    return 0;
}