Description

“那天TA说TA要来,于是我就来啦。
那天我说我要来,于是你就来啦。
TA看到了什么?
你又看到了什么?
我看到你们在一起,我是真的很happy:)
太阳在哪里啊?
就在早上七八点。
太阳在哪里啊?
就在云的栖息地!”
——2050主题曲

2050的线下活动吸引了很多心怀梦想的年轻人。

小伙们打算组团去参加。他们一共有 n+m+2k 个人,包括 n+k 个男生,m+k 个女生,其中 k 对男女生为异性情侣,现在他们要找房间住。房间有三种类型,双人间 a 元一间,三人间 b 元一间,这两种只能同性一起住。情侣间能住一对异性情侣,一间 c 元。除了情侣间以外,其他房间都可以不住满。

求最少花多少钱,能让小伙伴们都有地方住。

Input
第一行一个整数 T (1≤T≤50) 表示数据组数。 接下来 T 组数据,每组数据一行 6 个整数 n,m,k,a,b,c,其中 0≤n,m,k≤103,0≤a,b,c≤109。

Output
对于每组数据输出一行一个数,表示所有人住下来所需要的最小花费。

Sample Input

2
3 0 1 1 3 3
3 3 2 1 6 2

Sample Output

3
6

思路:先不考虑情侣房,开一个数组f[i]表示i个人住双人间或三人间的最少花费,枚举f[i] (0<=i<=N+M+2*K+10 ),然后再考虑住情侣房的情况,枚举i (0<=i<=k)对情侣住情侣房,此时花费为: i *c+f[n+k-i]+f[m+k-i],取最小值输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#define mem(a, b) memset(a, b, sizeof(a))
#define PI 3.1415926535
using namespace std;
typedef long long ll;
const int MAXn = 4e3 + 10;

ll f[MAXn];

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int i, m, n, k, a, b, c;
scanf("%d%d%d%d%d%d", &n, &m, &k, &a, &b, &c);
for ( i = 0; i < MAXn; i++)
{
f[i] = 0x3f3f3f3f3f3f3f3f;
}
f[0]=0;
for(i=2;i<n+2*k+m+15;i++)
{//住双人间
f[i]=min(f[i],f[i-2]+a);
}//类似背包问题,物品体积为2 费用为a
for(i=3;i<m+2*k+n+15;i++)
{//三人间
f[i]=min(f[i],f[i-3]+b);
}
for(i=m+n+2*k+14;i>=0;i--)
{//考虑没住满的情况
f[i]=min(f[i],f[i+1]);
}
ll ans=0x3f3f3f3f3f3f3f3f;
for(i=0;i<=k;i++)
{
ans=min(ans,i*c+f[n+k-i]+f[m+k-i]);//枚举情侣房
}
printf("%lld\n",ans);
}
}

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号