2018年2/3月月赛 Day1 行军(改) 题解

2018年2/3月月赛 Day1 行军(改) 题解

题目背景

再过十几天,人类远征军就要出发去讨伐星神(visitor)了。

正规勇者莉莉娅·阿斯普雷伊及一众准勇者们正在为行军问题而焦头烂额。

“这么多的粮草,还有那么远的路,这该怎么办啊?”莉莉娅抱怨道。

你能帮帮莉莉娅吗?

题目描述

从皇都到达星神居住地,这之间有无数座城市和无数条道路,将会消耗很多时间。

而为了保证军士们的生活,需要带上足够的粮草。

皇都共有n堆粮草可供选择,每堆粮草有重量p,体积q和价值w,而为了便于行军,莉莉娅只能选择不超过u重量且不超过v体积的粮草带走。

输入输出格式

输入格式

第一行,包含三个正整数,分别为粮草数量n,最大载重量u,最大体积v。

接下来n行,每行包含三个正整数p[i]、q[i]和w[i]。

第i+1行的p[i]表示第i堆粮草的重量,q[i]表示第i堆粮草的体积,w[i]表示第i堆粮草的价值。

输出格式

一行,输出能载的粮草的最大价值。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
6 10 10
1 1 1
2 3 1
3 2 1
2 5 1
5 2 1
4 3 1

输出样例#1:

1
4

输入样例#2:

1
2
3
4
5
6
7
8
9
10
11
10 16 24
2 9 4
5 6 5
3 7 3
6 2 9
7 6 5
7 5 6
3 3 8
1 4 1
9 5 9
9 7 6

输出样例#2:

1
26

说明

1<=n<=1000,1<=u<=1000,1<=v<=1000

所有数据不大于maxint

非常简单的一个二维约束的背包问题。解题方法详见这里

数据较大,最好scanf输入。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
using namespace std;
int n,u,v;
int p[1010],q[1010],w[1010],f[1010][1010]={0};
int main()
{
int i,j,k;
cin>>n>>u>>v;
for(i=1;i<=n;i++) scanf("%d%d%d",&p[i],&q[i],&w[i]);
for(i=1;i<=n;i++)
{
for(j=u;j>=p[i];j--)
{
for(k=v;k>=q[i];k--)
{
int temp=f[j-p[i]][k-q[i]]+w[i];
if(f[j][k]<temp) f[j][k]=temp;
}
}
}
cout<<f[u][v];
return 0;
}
--It's the end.Thanks for your read.--