首页 > 代码库 > poj2901 Hotel
poj2901 Hotel
Hotel
| Time Limit: 10000MS | Memory Limit: 65536K | |
| Total Submissions: 859 | Accepted: 280 |
Description
Zebel, the tour coordinator, has reserved a limited number of hotel rooms for his clients. Rooms have different capacities and naturally, different prices. Zebel decides to find the least cost assignment of the tour participants to the available rooms. His strategy is to fill the rooms with appropriate collection of people to minimize the overall room cost, but he is facing some restrictions that no two people of different sex that are not married may stay in the same room, and if a room is assigned to a married couple, no other person may stay in that room. Note that it is not necessary to put a married couple in the same room. It is also possible that we do not fill a room to its capacity.
You are to write a program to help Zebel find a least cost assignment of the tour participants to the reserved hotel rooms.
You are to write a program to help Zebel find a least cost assignment of the tour participants to the reserved hotel rooms.
Input
The only number in the first line is t, the number of test cases that follow. The first line of each test case contains four integer numbers, 0 ≤ m ≤ 500 the number of male tour participants, 0 ≤ f ≤ 500 the number of female tour participants, 0 ≤ r ≤ 500 the number of rooms reserved by Zebel, and c ≥ 0 which is the number of marriage relations between tour participants. Note that polygamy is not allowed in the tour; i.e. each participant is either single or has a unique mate.
The description of the reserved rooms comes on the following r lines. Each line describes a room, by two integer numbers 1 ≤ bi ≤ 5, and 1 ≤ pi ≤ 1000, which are the capacity and price of this room.
The description of the reserved rooms comes on the following r lines. Each line describes a room, by two integer numbers 1 ≤ bi ≤ 5, and 1 ≤ pi ≤ 1000, which are the capacity and price of this room.
Output
For each test case in the input, output the minimum cost of assigning the rooms to the tour participants. If this is not possible, output the phrase "Impossible" instead.
Sample Input
22 1 3 13 52 102 41 1 1 01 4
Sample Output
9Impossible
Source
Tehran 2005
题意：有n个男人，m个女人一起住宿，其中有r个房间，这些人中有c对夫妇。每对夫妇在一间房间的时候房间不能有其他人，不是一对的男女不能同房。没有一夫多妻、一妻多夫。每个房间有容量bi，有费用pi。请问让全部人住进去最少需要多少钱。
思路：如果有两对夫妇的话，分别需要2+2的房间，如果把他们分成2男2女，也是分成2+2的房间，且房间还可能住其他人，所以显然更优，所以最优的情况下最多只有c%2的夫妇住在一起，那么只要用动态规划计算没有夫妻住在一起的情况和只有一对夫妻住在一起的情况就行了。用 f[i][j]表示i个男人，j个女人住在旅馆里最少需要多少钱。思路很简单，直接看代码就能懂了。
1 /* 2 * Author: Joshua 3 * Created Time: 2014年10月06日 星期一 14时25分35秒 4 * File Name: poj2901.cpp 5 */ 6 #include<cstdio> 7 #include<algorithm> 8 #include<cstring> 9 #include<iostream>10 using namespace std;11 #define maxn 51512 #define inf 0x3f3f3f3f13 typedef long long LL;14 int T,n,m,r,c,ans;15 int b[maxn],p[maxn],f[maxn][maxn];16 17 void init()18 {19 scanf("%d%d%d%d",&n,&m,&r,&c);20 for (int i=1;i<=r;++i)21 scanf("%d%d",&b[i],&p[i]);22 }23 24 void updata(int&x ,int y)25 {26 if (y<x) x=y;27 }28 29 void solve()30 {31 int tb,tp,tans,tk;32 ans=inf;33 for (int i=0;i<=n+10;++i)34 memset(f[i],0x3f,(m+10)<<2);35 f[0][0]=0;36 for (int i=1;i<=r;++i)37 {38 tb=b[i];tp=p[i]; 39 for (int t1=n+5;t1>=0;t1--)40 for (int t2=m+5;t2>=0;t2--)41 {42 if (tb<=t1) updata(f[t1][t2],f[t1-tb][t2]+tp);43 if (tb<=t2) updata(f[t1][t2],f[t1][t2-tb]+tp);44 }45 }46 for (int i=n;i<=n+5;++i)47 for (int j=m;j<=m+5;++j)48 ans=min(ans,f[i][j]);49 if (c%2==0) return;50 tk=0;51 b[0]=6;p[0]=inf;52 for (int i=1;i<=r;++i)53 if (b[i]>=2 && (p[i]<=p[tk] || (p[i]==p[tk] && b[i]<b[tk])))54 tk=i;55 if (!tk) return;56 n--;m--;57 for (int i=0;i<=n+10;++i)58 memset(f[i],0x3f,(m+10)<<2);59 f[0][0]=0;60 for (int i=1;i<=r;++i)61 {62 if (i==tk) continue;63 tb=b[i];tp=p[i]; 64 for (int t1=n+5;t1>=0;t1--)65 for (int t2=m+5;t2>=0;t2--)66 {67 if (tb<=t1) updata(f[t1][t2],f[t1-tb][t2]+tp);68 if (tb<=t2) updata(f[t1][t2],f[t1][t2-tb]+tp);69 }70 }71 for (int i=n;i<=n+5;++i)72 for (int j=m;j<=m+5;++j)73 ans=min(ans,f[i][j]+p[tk]);74 }75 76 int main()77 {78 scanf("%d",&T);79 for (int i=1;i<=T;++i)80 {81 init();82 solve();83 if (ans!=inf) printf("%d\n",ans);84 else printf("Impossible\n");85 }86 return 0;87 }
poj2901 Hotel
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。