记录编号	238412	评测结果	AAAAA
题目名称	[冲刺NOIP2014]编码	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-03-19 08:34:06	内存使用	0.33 MiB

#include<cstdio>
#include<cstring>
char buf[2200],str[2250];
int f[2200];
struct code{
	char s[220];
	int len;
	int lens;
}lst[105];
bool at(int a,int b){
	int lim=a+lst[b].lens;
	for(int i=a;i<lim;++i)if(str[i]!=lst[b].s[i-a])return false;
	return true;
}
int min(int a,int b){
	return a<b?a:b;
}
void calc(int k){
	f[0]=0;int l=strlen(str);
	for(int i=0;i<l;++i){
		for(int j=0;j<k;++j){
			if(at(i+1,j)){
	//			printf("at%d %d ",i,j);
	//			printf("f[%d-1]==%d\n",i,f[i-1]);
				f[i+lst[j].lens]=min(f[i+lst[j].lens],f[i]+lst[j].len);
			}
		}
	}
}
int main(){
	freopen("compare.in","r",stdin);
	freopen("compare.out","w",stdout);
	int n;scanf("%d",&n);
	scanf("%s",buf);
	while(n--){
		memset(lst,0,sizeof(lst));
		memcpy(str+1,buf,sizeof(buf));
		str[0]='!';
		memset(f,127,sizeof(f));
		int k=0;
		while(scanf("%s",buf)!=EOF&&buf[0]=='('){
			int i;
			for(i=1;buf[i]!=',';++i){
				lst[k].s[i-1]=buf[i];	
				lst[k].lens++;
			}
			for(i=i+1;buf[i]!=')';++i){
				lst[k].len++;
			}
			k++;
		}
		calc(k);
		int tmp=strlen(str)-1;
		if(f[tmp]==2139062143)f[tmp]=0;
		printf("%d\n",f[tmp]);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}