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

古韵之刺绣"/>

【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


比赛的时候根本看不出来是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[3];int chua[3];int vhua[3];int v[N];int c[N];int vbu[N];int num2[N];REP(i,3)RIII(num[i],chua[i],vhua[i]);REP(i,n){RII(vbu[i],num2[i]);REP(j,3)if(num[j]==num2[i]){c[i]=chua[j]*vbu[i];v[i]=vbu[i]+vbu[i]*vhua[j];}}int dp[8005];CLR(dp,0);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;
}

转载于:.html