UVa 565 - Pizza Anyone?

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=506

类型： 暴力枚举，搜索

题目：

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.

题目大意：

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

分析与总结：

题目只有16种东西选择， 对于每种东西之是选择或者不选泽两种状态。那么用暴力枚举法完全可以做出。

用一个数字，它的各个二进制位表示定或者不定。枚举0 ～ (1<<16)-1即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[100][100];
int nIndex;


int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    while(gets(str[0])){
        nIndex = 1;
        while(gets(str[nIndex]), str[nIndex++][0]!='.') ;;

        int status=0;
        bool flag=true;
        int maxNum = (1<<16)-1;
        while(status <= maxNum){

            flag = true;
            for(int i=0; i<nIndex-1; ++i){
                bool ok = false;
                int pos=0;
                while(pos < strlen(str[i])){
                    if(str[i][pos]=='+'){
                        if((status >> (str[i][pos+1]-'A')) & 1 ){ 
                            ok = true; break;
                        }
                    }
                    else if(str[i][pos]=='-'){
                        if( !((status >> (str[i][pos+1]-'A')) & 1)){
                            ok = true;
                            break;
                        }
                    }
                    pos += 2;
                }
                if(!ok){flag=false ; break; }
            }
            if(flag) break;
            ++status;
        }
        if(!flag) printf("No pizza can satisfy these requests.\n") ;
        else{
            int pos=0;
            printf("Toppings: ");
            while(pos <16){
                if(status & 1) printf("%c", pos+'A');
                ++pos; status >>= 1;
            }
            printf("\n");
        } 
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

    

  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)