终极装备

题目

【问题大意】
小明玩游戏时,获得了一些终极装备,但在这之前,他已经获得了一批能和终极装备媲美的装备,并且前后的数量是一致的,但人物的最大负重为M,每个装备可提升人物V[i]力量值,自身重量为W[i](我们把这两个值称为该装备的属性),现在的目的是让人物更强大
【输入】
第一行3个数:M,N,T。分别为最大负重、装备数量、人物不带任何装备的能量值。
接下来N行,一行4个数,V1[i],W1[i],V2[i],W2[i](前后两组装备视为同种)
【输出】
人物能够达到的最大力量值,并且同种装备只能选一个。
【样例输入】
50 3 20
12 18 23 19
17 10 30 24
20 20 17 20
【样例输出】
80
【数据范围】
(其实这个贴出来没什么用)
1<=M,T<=10000,1<=N<=200
1<=W[i],V[i]<=10000

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int f[10010];//f[I]=当使用I重量时,可以达到的能量
int main(int argc,char *argv[])
{
int m,n,t;
scanf("%d %d %d",&m,&n,&t);
for(int i=1;i<=n;i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(b>d) { int t=a;a=c;c=t;t=b;b=d;d=t; }
v1[i]=a;v2[i]=c;w1[i]=b;w2[i]=d;
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w1[i];j--)
if(j>=w2[i]) f[j]=max3(f[j],f[j-w1[i]]+v1[i],f[j-w2[i]]+v2[i]);
else f[j]=max2(f[j],f[j-w1[i]]+v1[i]);
}
printf("%d",f[m]+t);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/35a8.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%