记录编号	117563	评测结果	AAAAAAAAAA
题目名称	[USACO Feb07] 掷骰子	最终得分	100
用户昵称	任杰	是否通过	通过
代码语言	C++	运行时间	0.160 s
提交时间	2014-08-30 13:51:12	内存使用	14.36 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAX_N 20
#define MAX_E 20

struct COND
{
	int times[MAX_N],face[MAX_N];
	int cnt;
} Cond[100000];
int condcnt=0;

int N,S,E;
char exp[100];
int cur;
int curID;
int seqcnt=0;
int curseq[MAX_N];
int numhash[MAX_N+1];

int GetANum()
{
	int ret;

	while(exp[cur]<'0' || exp[cur]>'9')
	{
		cur++;
	}

	ret=0;
	while(exp[cur]>='0' && exp[cur]<='9')
	{
		ret=ret*10+exp[cur]-'0';
		cur++;
	}

	while(exp[cur] && (exp[cur]<'0' || exp[cur]>'9')) cur++;

	return ret;
}

void GetCond()
{
	char *pFind=strchr(exp,'+');
	int &cnt=Cond[condcnt].cnt;
	int times,face;

	cnt=0;
	cur=0;

	while(pFind)
	{
		times=GetANum();
		face=GetANum();

		Cond[condcnt].times[cnt]=times;
		Cond[condcnt].face[cnt]=face;
		cnt++;
		pFind=strchr(&exp[cur],'+');
	}
	times=GetANum();
	face=GetANum();

	Cond[condcnt].times[cnt]=times;
	Cond[condcnt].face[cnt]=face;
	cnt++;

	condcnt++;
}

bool OK()
{
	memset(numhash,0,sizeof(numhash));
	for(int i=0;i<N;i++)
	{
		numhash[curseq[i]]++;
	}

	for(int i=0;i<condcnt;i++)
	{
		int okcnt=0;
		int cnt=Cond[i].cnt;
		for(int j=0;j<cnt;j++)
		{
			if(numhash[Cond[i].face[j]]>=Cond[i].times[j]) okcnt++;
			if(okcnt>=cnt)
			{
				return true;
			}
		}
	}

	return false;
}

void dfs(int cur)
{
	if(cur==N)
	{
		if(OK()) seqcnt++;
		return;
	}

	for(int i=1;i<=S;i++)
	{
		curseq[cur]=i;
		dfs(cur+1);
	}
}

int main()
{
	freopen("cowyotz.in","r",stdin);
	freopen("cowyotz.out","w",stdout);

	scanf("%d%d%d",&N,&S,&E);

	for(int i=0;i<E;i++)
	{
		scanf("%s",exp);
		GetCond();
	}
	dfs(0);
	printf("%d\n",seqcnt);

	return 0;
}