记录编号	86555	评测结果	AAAAAAAAAA
题目名称	[NOI 2000]古城之谜	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2014-01-26 17:15:04	内存使用	1.67 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<vector>
using namespace std;
const int SIZEC=30;
//由于本题的特殊性,存储的TRIE树实际上是倒着来的,即从最后一个字母到第一个字母
class TRnode{
public:
	char data;
	bool type[3];//按顺序是:名词,动词,辅词
	int son[SIZEC];
	TRnode(){
		data='0';
		for(int i=0;i<3;i++) type[i]=false;
		for(int i=0;i<SIZEC;i++) son[i]=-1;
	}
	void build(string,char);
	void print(void){//调试接口,输出节点信息
		cout<<"data:"<<data<<endl;
		for(int i=0;i<3;i++) cout<<type[i]<<" ";cout<<endl;
		for(int i=0;i<26;i++){
			if(son[i]!=-1){
				cout<<char(i+'a')<<":"<<son[i]<<endl;
			}
		}
	}
};
TRnode trie[1000*20+1];
int tot=0;
#define root trie[0]
void TRnode::build(string str,char pro){
	if(!str.size()){//到头了,需要标记词性
		if(pro=='n') type[0]=true;
		else if(pro=='v') type[1]=true;
		else if(pro=='a') type[2]=true;
		return;
	}
	if(son[str[0]-'a']==-1){//创建子节点
		son[str[0]-'a']=tot+1;
		TRnode temp;
		temp.data=str[0];
		trie[tot+1]=temp;
		tot++;
	}
	string next=str;next.erase(next.begin());//去掉首字母
	trie[son[str[0]-'a']].build(next,pro);
}
class SV{
public:
	int s,w;//句子数和单词数
	void print(void){
		cout<<s<<endl<<w<<endl;
	}
};
bool operator < (SV a,SV b){
	if(a.s<b.s) return true;
	if(a.s>b.s) return false;
	return a.w<b.w;
}
SV operator + (SV a,SV b){return (SV){a.s+b.s,a.w+b.w};}
SV min(SV a,SV b){return a<b?a:b;}
int N;//单词个数
const int SIZEM=7000,INF=0x7fffffff/2;
int M;//文章长度
string text;//文章
SV f[2][SIZEM];//0是名词,1是动词
void printtext(int x,int y){//输出text中[x,y]之间的部分
	for(int i=x;i<=y;i++) cout<<text[i];
}
void DP(void){
	for(int i=0;i<=M;i++) f[0][i]=f[1][i]=(SV){INF,INF};
	f[1][0]=(SV){1,0};
	for(int i=1;i<=M;i++){
		int tpos=0,j=i;
		while(true){
			if(j<=0) break;
			tpos=trie[tpos].son[text[j]-'a'];
			j--;//现在,j+1~i是一个单词了
			if(tpos==-1) break;
			if(trie[tpos].type[0]){//这是一个名词
				f[0][i]=min(f[0][i],f[0][j]+(SV){1,1});
				f[0][i]=min(f[0][i],f[1][j]+(SV){0,1});
			}
			if(trie[tpos].type[1]){//这是一个动词
				f[1][i]=min(f[1][i],f[0][j]+(SV){0,1});
			}
			if(i<M&&trie[tpos].type[2]){//这是一个辅词 
				f[1][i]=min(f[1][i],f[1][j]+(SV){0,1});
				f[0][i]=min(f[0][i],f[0][j]+(SV){0,1});
			}
		}
	}
	min(f[0][M],f[1][M]).print();
}
void init(void){
	TRnode temp;
	trie[0]=temp;
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		string line,str="\0";
		cin>>line;
		for(int i=line.size()-1;i>=2;i--) str+=line[i];
		trie[0].build(str,line[0]);
	}
	cin>>text;
	M=text.size()-1;
	text=" "+text;//这样text的下标就从1开始了
}
int main(){
	freopen("lostcity.in","r",stdin);
	freopen("lostcity.out","w",stdout);
	init();
	DP();
	return 0;
}