2009年南海初中竞赛 比萨

题目

解题思路

深度优先搜索。

代码

#include<cstdio>
#include<cstring>
using namespace std; 
int n,t,ans; bool tg[101]; 
struct node{int len; bool b[101]; 
}a[101];bool ok(int lgg)//这个方案是否可行
{for (int j=1;j<=n;j++){int sum=0; for (int i=1;i<=t;i++)if (tg[i]&&a[j].b[i]) sum++; //不能一起的都有时，就返回falseif (sum==a[j].len) return false; }return true; //否则返回true
}void dfs(int lle)
{   ans++; //累加方案数for (int i=lle+1;i<=t;i++)//去重，或者用hash{tg[i]=true;if (ok(i)) dfs(i);tg[i]=false; }
}
int main()
{freopen("pizza.in","r",stdin); freopen("pizza.out","w",stdout); scanf("%d%d",&t,&n); for (int i=1;i<=n;i++){scanf("%d",&a[i].len); int q; for (int j=1;j<=a[i].len;j++)scanf("%d",&q),a[i].b[q]=true;//读入&&初始化}dfs(0); //搜到第几位printf("%d",ans); //输出
}