记录编号	185726	评测结果	AAAAAAAAAA
题目名称	[NOI 2000]古城之谜	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2015-09-08 18:50:28	内存使用	2.51 MiB

#include<cstdio>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
using namespace std;
const int SIZEC=30,SIZEM=7000,INF=0x7fffffff/2;
int N;
string txt;//待处理文本
class miku//字典树
{
public:
	char a;
	bool type[3];
	int link[SIZEC];
	miku()
	{
		a='0';
		for(int i=0;i<3;i++) type[i]=0;
		for(int i=0;i<26;i++) link[i]=-1;
	}
	void build(string str,int t);
	void print()
	{
		cout<<"date:"<<a<<endl;
		for(int i=0;i<3;i++) cout<<type[i]<<" ";
		cout<<endl;
		for(int i=0;i<26;i++) if(link[i]!=-1) cout<<char(i+'a')<<" "<<link[i]<<endl;
		cout<<endl;
	}
};
miku T[1000*20+10];
int tot=0;
void miku::build(string str,int pro)
{
	if(!str.size())
	{
		if(pro==0) type[0]=1;
		else if(pro==1) type[1]=1;
		else if(pro==2) type[2]=1;
		else cout<<"error"<<endl;
		return;
	}
	if(link[str[0]-'a']==-1)
	{
		tot++;
		link[str[0]-'a']=tot;
		T[tot].a=str[0];
	}
	string next=str;next.erase(next.begin());
	T[link[str[0]-'a']].build(next,pro);
}
class poi
{
public:
	int S;//句子数
	int V;//单词数
	void print()
	{
		printf("%d\n%d\n",S,V);
	}
};
bool operator < (poi a,poi b)
{
	if(a.S<b.S) return 1;
	if(a.S>b.S) return 0;
	return a.V<b.V;
}
poi min(poi a,poi b)
{
	if(a<b) return a;
	else return b;
}
poi operator +(poi a,poi b)
{
	poi	c;
	c.S=a.S+b.S;c.V=a.V+b.V;
	return c;
}
poi f[2][SIZEM];//0代表以名词为结尾，1代表以动词为结尾
void init()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		string str="\0",line;
		int type;
		cin>>line;
		for(int j=2;j<line.length();j++)
		{
			str=str+line[j];
		}
		if(line[0]=='n') type=0;
		else if(line[0]=='v') type=1;
		else if(line[0]=='a') type=2;
		else cout<<"error"<<endl;
		T[0].build(str,type);
	}
	cin>>txt;
	txt=" "+txt;
}
void DP()
{
	int M=txt.size()-1;
	for(int i=0;i<=M;i++) f[1][i]=f[0][i]=(poi){INF,INF};
	f[1][0].S=1;f[1][0].V=0;
	for(int i=0;i<M;i++)
	{
		int j=i,now=0;
		//cout<<txt[i]<<endl;
		while(true)//把txt[i+1]到j进行匹配
		{
			j++;
			if(j>=txt.size()-1) break;
			if(T[now].link[txt[j]-'a']==-1) break;
			now=T[now].link[txt[j]-'a'];
			if(T[now].type[0]==1)//是一个名词
			{
				f[0][j]=min(f[0][i]+(poi){1,1},f[0][j]);
				f[0][j]=min(f[1][i]+(poi){0,1},f[0][j]);
			}
			if(T[now].type[1]==1)//是一个动词
			{
				f[1][j]=min(f[0][i]+(poi){0,1},f[1][j]);
			}
			if(j<M-1&&T[now].type[2]==1)//是一个副词
			{
				f[1][j]=min(f[1][i]+(poi){0,1},f[1][j]);
				f[0][j]=min(f[0][i]+(poi){0,1},f[0][j]);
			}
		}
	}
	min(f[0][M-1],f[1][M-1]).print();
}
int main()
{
	freopen("lostcity.in","r",stdin);
	freopen("lostcity.out","w",stdout);
	init();
	DP();
	return 0;
}