[UVA][greedy] 11493 - The Club Ballroom
The Club Ballroom
| The Club Ballroom |
The Problem
The Tingua Social Club is building its new ballroom. The club members wish to have the floor covered with wood planks, as they consider this to be the best for dancing. A lumberyard from the region donated a large quantity of good quality wooden planks to be used in the ballroom. The donated planks have all the same width, but have different lengths.
The ballroom is a rectangle of dimensions N x M meters. The planks must be placed juxtaposed, so that no plank superposes another, and the whole floor must be covered. They must be aligned, lengthwise, to one of the sides of the ballroom, and all planks must be parallel. The club members do not want too many joints in the floor, and therefore if a plank is not long enough to cover the distance between two opposite sides of the ballroom, it can be joined to at most one other plank to complete the distance. Furthermore, the chief-carpenter has a great respect for all woods, and would rather not saw any plank. Therefore, he wants to know whether it is possible to cover the floor with the set of planks donated, observing the restrictions described; in case it is possible, the chief-carpenter wish to know the smallest number of planks he can use.
The figure below depicts two possible ways to cover the floor of a ballroom with dimensions 4 x 5 meters for a set of ten donated planks, with 100 cm width, and lengths 1, 2, 2, 2, 2, 3, 3, 4, 4 and 5 meters.
The Input
The input contains several test cases. The first line of a test case contains two integers N and M indicating the dimensions, in meters, of the ballroom (1 ≤ N,M ≤ 104). The second line contains one integer L representing the planks width, in centimeters (1 ≤ L ≤ 100). The third line contains one integer K, indicating the number of planks donated (1 ≤ K ≤ 105). The fourth line contains K integers Xi, separated by spaces, representing the length, in meters, of one plank (1 ≤ Xi ≤ 104 for 1 ≤ i ≤ K). The end of input is indicated by a line containing only two zeros, separated by one space.
The Output
For each of the test cases in the input your program must print one single line, containing one integer, the smallest number of planks needed to cover the whole floor, satisfying the restrictions established. If it is not possible to cover the whole floor satisfying the restrictions established, print one line with the word "impossivel" (which means impossible in Portuguese).
Sample Input
4 5 100 10 1 2 2 2 2 3 3 4 4 5 5 4 100 7 4 5 4 4 4 4 3 4 5 99 4 4 4 4 4 3 2 100 7 2 4 1 4 2 4 4 0 0
Sample Output
7 5 impossivel impossivel
題目描述：
現在要鋪設舞廳地板，考慮直鋪或者橫鋪，而每鋪同一條時，最多使用 2 個來完成。
大於等於 3 個是不行的，求最少鋪設個數。
題目解法：題目要求相當多，還以為是要使用 bitmask dp 的做法，後來發現數據大到不可行。
還是要看懂題目才方便寫題啊。
先嘗試使用 1 個可以鋪設一條的情況，盡可能地完成。
最後再來考慮 2 個鋪一條的情況。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int pcount[10005];
int greedy(int row, int width) {
int ret = 0, i;
static int buf[10005];
memcpy(buf, pcount, sizeof(pcount));
while(row > 0 && buf[width])
row--, ret++, buf[width]--;
for(i = 1; i < width; i++) {
while(row > 0 && buf[i]) {
buf[i]--;
if(buf[width-i]) {
row--, ret += 2, buf[width-i]--;
}
}
}
return row ? 0xfffffff : ret;
}
int main() {
int N, M, L, K;
int i, j, k, x;
while(scanf("%d %d", &N, &M) == 2 && N+M) {
scanf("%d %d", &L, &K);
memset(pcount, 0, sizeof(pcount));
for(i = 0; i < K; i++) {
scanf("%d", &x);
pcount[x]++;
}
int ret = 0xfffffff;
if(N*100%L == 0)
ret = min(ret, greedy(N*100/L, M));
if(M*100%L == 0)
ret = min(ret, greedy(M*100/L, N));
if(ret != 0xfffffff)
printf("%d\n", ret);
else
puts("impossivel");
}
return 0;
}