UVA - 565 Pizza Anyone?（状态压缩+暴利枚举）

admin管理员组

文章数量:1648552

Pizza Anyone?

You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?

The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:

Input Code	Topping
A	Anchovies
B	Black Olives
C	Canadian Bacon
D	Diced Garlic
E	Extra Cheese
F	Fresh Broccoli
G	Green Peppers
H	Ham
I	Italian Sausage
J	Jalapeno Peppers
K	Kielbasa
L	Lean Ground Beef
M	Mushrooms
N	Nonfat Feta Cheese
O	Onions
P	Pepperoni

Your friends provide you with a line of text that describes their pizza preferences. For example, the line

+O-H+P;

reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line

-E-I-D+A+J;

indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.

Input 

The input consists of a series of pizza constraints.

A pizza constraint is a list of 1 to 12 topping constraint lists each on a line by itself followed by a period on a line by itself.

A topping constraint list is a series of topping requests terminated by a single semicolon.

An topping request is a sign character (+/-) and then an uppercase letter from A to P.

Output 

For each pizza constraint, provide a description of a pizza that satisfies it. A description is the string ``  Toppings:  " in columns 1 through 10 and then a series of letters, in alphabetical order, listing the toppings on the pizza. So, a pizza with onion, anchovies, fresh broccoli and Canadian bacon would be described by:

Toppings: ACFO

If no combination toppings can be found which satisfies at least one request of every person, your program should print the string

No pizza can satisfy these requests.

on a line by itself starting in column 1.

Sample Input 

+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+P-O;
+O+J-F;
+H+I+C;
+P;
+O;
+O+M+L;
-O-P;
+M-L+P;
.

Sample Output 

Toppings:
Toppings: CELP
No pizza can satisfy these requests.

题目大意：
你负责去订购一个大比萨， 你的朋友们对于要添加什么或者不添加什么都有不同的要求。但是你的朋友们也知道不可能满足全部的要求。所以你要选择一个订购方案，让所有人至少满足其中一个要求。 注意，如果某人不想要哪个，那么不添加那个也算是满足了他的一个要求。


分析与总结：
题目只有16种东西选择， 对于每种东西之是选择或者不选泽两种状态。那么用暴力枚举法完全可以做出。
用一个数字，它的各个二进制位表示定或者不定。枚举0 ～ (1<<16)-1即可。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int N = 100;
char str[N][N];
inline bool judge(int status,int cur) {
	int len = strlen(str[cur]);
	for (int pos = 0; pos < len; pos += 2) {
		if(str[cur][pos] == '+') {
			if((status >> (str[cur][pos+1]) - 'A') & 1) {
				return true;
			}
		}else if(str[cur][pos] == '-') {
			if(~(status >> (str[cur][pos+1] - 'A')) & 1) {
				return true;
			}
		}
	}
	return false;
}
int main() {
	int cnt = 0;
	while(scanf("%s",str[cnt]) != EOF) {
		if(str[cnt][0] == '.') {
			int status;
			bool flag;
			for (status = 0; status < 1<<16; status++) {
				flag = true;
				for (int i = 0; i < cnt; i++) {
					bool ok = judge(status,i); //判断是否符合要求，如果有一个不符合要求就退出
					if (!ok) {
						flag = false;
						break;
					}
				}
				if(flag) {
					break;
				}
			}
			if(!flag) {
				printf("No pizza can satisfy these requests.\n");
			}else {
				printf("Toppings: ");
				for(int i = 0; i < 16; i++) {
					if(status & 1) {
						printf("%c",i+'A');
					}
					status >>= 1;
				}
				printf("\n");
			}
			cnt = -1;
		}
		cnt++;
	}
	return 0;
}

本文标签： 暴利状态uvaPizza