題目大意：你需要制作一個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 閱讀(413)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索