首页 > 代码库 > 古韵之刺绣 embro

古韵之刺绣 embro

【题目描述】:

日暮堂前花蕊娇,

争拈小笔上床描,

绣成安向春园里,

引得黄莺下柳条。

——胡令能《咏绣障》

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

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

 

【输入描述】:

第一行为两个数n(布的匹数,0<n<=100)、m(包的容积,0<m<=8000);

第二行到第四行,每行有3个数据:花纹种类编号z0<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的包里所能装下作品的最大美观度。

 

【样例输入】

【样例输出】

5 100

8 2001 5

4 9 8

3 74 4

111 4

79 8

6 3

5 8

23 4

10449

【数据范围及描述】:

 

动态规划水题,不讲

技术分享
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 typedef long long LL; 8  9 const int maxm=8005;10 const int maxn=105;11 12 LL cost[maxn],val[maxn];13 LL F[maxm];14 int N,M;15 16 struct node17 {18     int z,c,v;19     bool operator<(node p)const{return z<p.z;}20 }A[4];21 22 int bfind(int x)23 {24     if(A[2].z==x) return 2;25     if(A[2].z<x) return 3;26     return 1;27 }28 29 int main()30 {31     scanf("%d %d",&N,&M);32     for(int i=1;i<=3;i++)33         scanf("%d %d %d",&A[i].z,&A[i].c,&A[i].v);34     sort(A+1,A+4);35     int id;36     LL s;37     for(int i=1;i<=N;i++)38     {39         scanf("%lld %d",&s,&id);40         id=bfind(id);41         val[i]=s*A[id].c;42         cost[i]=s+A[id].v*s;43     }44     for(int i=1;i<=N;i++)45         for(int j=M;j>=cost[i];j--)46             F[j]=max(F[j],F[j-cost[i]]+val[i]);47     printf("%d",F[M]);48     return 0;49 }
View Code

技术分享

 

古韵之刺绣 embro