题目大意：你需要制作一个Pizza，它能够满足所有人的至少一个要求。
一开始一直在枚举每一种材料是否被选择，TLE。后来改变思路，枚举每个人的需求：每个人可以什么都不选，可以选择一个或者多个，使自己的需求得到满足。尽管可以选择多个，但选择一个就够了，不需要多选。
第一种方法过样例用了0.1s，第二种方法过全部数据用了0.18s。
以下是我的代码：
//#define LOCAL
#include<stdio.h>
#include<string.h>
#ifdef LOCAL
#include<time.h>
#endif
const char End_Sign[]=".";
const long maxn=108,kind=16;
long num,inf[maxn][kind+1];
char str[50];
bool find,choose[kind+1],ans[kind+1];
long h(char *s,long pos)
{
if(s[pos-1]=='+') return s[pos]-'A'+1;
return -(s[pos]-'A'+1);
}
bool ok_one(long x)
{
for(long i=1;i<=kind;i++)
if((inf[x][i]==1&&choose[i])||(inf[x][i]==-1&&!choose[i]))
return true;
return false;
}
void dfs(long dep)
{
if(find) return;
if(dep>num)
{
find=true;
for(long i=1;i<=kind;i++)
ans[i]=choose[i];
return;
}
if(ok_one(dep)) dfs(dep+1);
for(long i=1;i<=kind&&!find;i++)
{
if(inf[dep][i]==1&&!choose[i])
{
choose[i]=true;
dfs(dep+1);
choose[i]=false;
}
}
}
int main()
{
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
while(gets(str)!=0)
{
num=0;
find=false;
for(long i=1;i<maxn;i++)
for(long j=1;j<=kind;j++)
inf[i][j]=0;
// Clear
while(strcmp(str,End_Sign)!=0)
{
num++;
long i=0,t;
while(str[i]!=';')
{
t=h(str,i+1);
if(t>0) inf[num][t]=1;
else inf[num][-t]=-1;
i+=2;
}
gets(str);
}
// Read In and Init
for(long i=1;i<=kind;i++) choose[i]=false;
dfs(1);
// Dfs
if(find)
{
printf("Toppings: ");
for(long i=1;i<=kind;i++)
if(ans[i])
printf("%c",i+'A'-1);
putchar('\n');
}
else printf("No pizza can satisfy these requests.\n");
// Output
}
#ifdef LOCAL
printf("%.3lf\n",(double)clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
posted on 2010-01-10 16:09
lee1r 阅读(404)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索