[01背包]vijos1407 古韵之刺绣

古韵之刺绣"/>

[01背包]vijos1407 古韵之刺绣

P1407古韵之刺绣 Accepted 标签： [显示标签]

描述

日暮堂前花蕊娇，
争拈小笔上床描，
绣成安向春园里，
引得黄莺下柳条。

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

当衬衣公司的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

样例输入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背包，唯一变化就是用了结构体，要把花纹和布匹的相关内容整合一下

状态转移方程：f[j] = max{f[j], f[j-v[i]] + bea[i]};

注意：
1、输入数据都是整数；
2、每块布上，必须绣满刺绣；

（题意不够明确，这两个都没说

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
using namespace std;
//f[j] = max{f[j], f[j-v[i]] + bea[i]};
const int N = 110;
const int T = 8000+10;
int f[T];//f[j] 表示j容量最大美观度
int v[N];
int bea[N];
struct{int bea;int v;
}e[N];
int main()
{int n, m;int i, j;int a, b, c;scanf("%d%d", &n, &m);for(i = 1; i <= 3; i++){scanf("%d%d%d", &a, &b, &c);e[a].bea = b;e[a].v = c;}for(i = 1; i <= n; i++){scanf("%d%d", &a, &b);bea[i] = a * e[b].bea;v[i] = a + a * e[b].v;}for(i = 1; i <= n; i++)for(j = m; j >= v[i]; j--)f[j] = max(f[j], f[j-v[i]] + bea[i]);printf("%d", f[m]);return 0;
}

出现警告：

foo.cpp:18:5: warning: anonymous type with no linkage used to declare variable '<anonymous 
struct> e [110]' with linkage [enabled by default]
}e[N];
^

应该是说我没声明结构体名字，然后直接声明数组的行为不太好……