Description
著名的考古学家石教授在云梦高原上发现了一处古代城市遗址。让教授欣喜的是在这个他称为冰峰城(Ice-Peak City)的城市中有12块巨大石碑，上面刻着用某种文字书写的资料，他称这种文字为冰峰文。然而当教授试图再次找到冰峰城时，却屡屡无功而返。幸好当时教授把石碑上的文字都拍摄了下来，为了解开冰峰城的秘密，教授和他的助手牛博士开始研究冰峰文，发现冰峰文只有陈述句这一种句型和名词(n)、动词(v)、辅词(a)这三类单词，且其文法很简单： <文章> ::= <句子> { <句子> } <句子> ::= <陈述句> <陈述句> ::= <名词短语> { <动词短语> <名词短语> }[ <动词短语> ] <名词短语> ::= <名词> | [ <辅词> ] <名词短语> <动词短语> ::= <动词> | [ <辅词> ] <动词短语> <单词> ::= <名词> | <动词> | <辅词> 注：其中 <名词> 、 <动词> 和 <辅词> 由词典给出，“::=”表示定义为，“|”表示或，{}内的项可以重复任意多次或不出现，[]内的项可以出现一次或不出现。在研究了大量资料后，他们总结了一部冰峰文词典，由于冰峰文恰好有26个字母，为了研究方便，用字母a到z表示它们。冰峰文在句子和句子之间以及单词和单词之间没有任何分隔符，因此划分单词和句子令石教授和牛博士感到非常麻烦，于是他们想到了使用计算机来 帮助解决这个问题。假设你接受了这份工作，你的第一个任务是写一个程序，将一篇冰峰文文章划分为最少的句子，在这个前提下，将文章划分为最少的单词。
Input
输入文件第1行为词典中的单词数n(n<=1000)。输入文件第2行至第(n+1)行每行表示一个单词，形为“a.mot”， a表示词性，可能是n(名词),v（动词）,a（辅词）中的一个，mot为单词，单词的长度不超过20。拼写相同而词性不同的单词视为不同的单词，如输入示例中的n.kick与v.kick是两个不同的单词。输入文件第(n+2)行为需要划分的文章，以“.”结束。输入文件中的文章确保为冰峰文。文章是由有限个句子组成的，每个句子只包含有限个单词。文章长度不超过5KB。
Output
输出文件两行，每行一个整数。第1行为划分出来的句子数。输出文件第2行为划分出来的单词数。
Sample Input 1
11
n.table
n.baleine
a.silly
n.snoopy
n.sillysnoopy
v.is
v.isnot
n.kick
v.kick
a.big
v.cry
sillysnoopyisnotbigtablebaleinekicksnoopysillycry.Sample Output 1
2
9Hint
为了阅读方便，划分的单词用空格分隔，在单词右标出它的词性，每行写一个句子，用句号表示句子结束。输出对应的划分：sillysnoopy[n] isnot[v] big[a] table[n].baleine[n] kick[v] snoopy[n] silly[a] cry[v].如果用下面的划分：silly[a] snoopy[n] isnot[v] big[a] table[n].baleine[n] kick[v] snoopy[n] silly[a] cry[v].则划分的句子数仍为2个，但单词数却多了1个，为10个，显然应该按前者而不是后者划分。
分析：
做出这道题关键在于理解语法。其中名词短语和动词短语给出的都是递归定义，可以转化为更直观的，
<名词短语> ::= {<辅词>} <名词>，
<动词短语> ::= {<辅词>} <动词>，也就是以一个名词或动词结尾，前面可以加上任意多个辅词。而句子就是要以名词短语开头，后面的名词短语和动词短语交替出现。
分析出语法结构，就可以进行动态规划。定义词性
j={0,1,2,3}。
\(f[i][0][k]\)表示前i个字母，以i结尾的单词词性为n，构成了k个句子的最小单词数
\(f[i][1][k]\)表示前i个字母，以i结尾的单词词性为v，构成了k个句子的最小单词数
\(f[i][2][k]\)表示前i个字母，以i结尾的单词词性为a，后面该接v了，构成了k个句子的最小单词数
\(f[i][3][k]\)表示前i个字母，以i结尾的单词词性为a，后面该接n了，构成了k个句子的最小单词数
DP状态转移方程
枚举可能以i结尾的单词，设它的词性为type，前一个单词结尾为j。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N=1005,M=6010,inf=0x3f3f3f3f;
int n,m,maxlen,word[M][22],f[M][4][2],id;
char s[M];
struct tree
{
int d[26];
int op,c;
void clear()
{
memset(d,0,sizeof(d));
c=-1;op=0;
}
}a[25010];
void insert(char s[],int op)
{
int u=0,len=strlen(s),i,v;
for(i=0;i<len;i++)
{
v=s[i]-'a';
if(a[u].d[v]==0)
{
id++;a[id].clear();
a[u].d[v]=id;
a[id].c=v;
}
u=a[u].d[v];
}
a[u].op|=op;
}
int find(int l,int r)
{
int i,j,u=0,v;
for(i=l;i<=r;i++)
{
v=s[i]-'a';
if(a[u].d[v]==0) return 0;
u=a[u].d[v];
}
return a[u].op;
}
int main()
{
int i,j,k,c,p,ans2,ans1;
char s1[25];
bool first=true;
while(~scanf("%d\n",&n))
{
if(!first) printf("\n");
else first=false;
maxlen=0;
p=0;id=0;
a[0].clear();
memset(word,-1,sizeof(word));
memset(f,0x3f,sizeof(f));
for(i=1;i<=n;i++)
{
scanf("%s",s1);
k=strlen(s1);
maxlen=max(maxlen,k);
if(s1[0]=='n') insert(s1+2,1);
else if(s1[0]=='v') insert(s1+2,2);
else insert(s1+2,4);
}
scanf("%s",s+1);
m=strlen(s+1)-1;
ans2=inf,ans1=0;
f[0][0][0]=0;
p=0;
for(k=1;k<=m;k++)
{
c=p;p=1-p;
for(i=1;i<=m;i++)
{
f[i][0][p]=f[i][1][p]=f[i][2][p]=f[i][3][p]=inf;
for(j=i-1;j>=i-maxlen&&j>=0;j--)
{
if(word[j+1][i-j]==-1) word[j+1][i-j]=find(j+1,i);
int type=word[j+1][i-j];
if(type&1)
{
f[i][0][p]=min(f[i][0][p],f[j][1][p]+1);
f[i][0][p]=min(f[i][0][p],f[j][3][p]+1);
f[i][0][p]=min(f[i][0][p],f[j][0][c]+1);
f[i][0][p]=min(f[i][0][p],f[j][2][c]+1);
}
if(type&2)
{
f[i][1][p]=min(f[i][1][p],f[j][0][p]+1);
f[i][1][p]=min(f[i][1][p],f[j][2][p]+1);
}
if(type&4)
{
f[i][2][p]=min(f[i][2][p],f[j][0][p]+1);
f[i][2][p]=min(f[i][2][p],f[j][2][p]+1);
f[i][3][p]=min(f[i][3][p],f[j][1][p]+1);
f[i][3][p]=min(f[i][3][p],f[j][3][p]+1);
f[i][3][p]=min(f[i][3][p],f[j][0][c]+1);
f[i][3][p]=min(f[i][3][p],f[j][1][c]+1);
}
}
}
ans2=min(f[m][0][p],f[m][1][p]);
if(ans2!=inf)
{
ans1=k;
break;
}
}
printf("%d\n%d\n",ans1,ans2);
}
return 0;
}