描述
日暮堂前花蕊娇,
争拈小笔上床描,
绣成安向春园里,
引得黄莺下柳条。
——胡令能《咏绣障》
古时女子四德中有一项——女红。女红的精巧程度对于女子来说是十分重要的。韵哲君十分爱好女红,尤其是刺绣。
当衬衣公司的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 比赛的时候根本看不出来是01背包 感觉题目描述的有很多漏洞就没敢开
如果不把dp清零为wa三个点 所以要避免任何可能导致失分的操作。。。
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
//input
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s)
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 505
int main()
{
int n,m;
RII(n,m);
int num[];
int chua[];
int vhua[];
int v[N];
int c[N];
int vbu[N];
int num2[N];
REP(i,)
RIII(num[i],chua[i],vhua[i]);
REP(i,n)
{
RII(vbu[i],num2[i]);
REP(j,)
if(num[j]==num2[i])
{
c[i]=chua[j]*vbu[i];
v[i]=vbu[i]+vbu[i]*vhua[j];
}
}
int dp[];
CLR(dp,);
REP(i,n)
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i] ]+c[i] );
cout<<dp[m]<<endl;
}