讨论 / C++ AC 对
潘崇明 2016-02-06 18:48:59
点我顶贴 收藏 删除
#include <cstdio>

const int MAXN=50;

char v[26][26][MAXN+1];

char f[MAXN][MAXN][26];

char g[MAXN][MAXN];

int h[MAXN+1];

int N;

void Init()

{

int i;

char t[6],s[MAXN+1];

scanf("%s",s);

scanf("%d",&i);

for (;i;--i)

{

scanf("%s",t);

v[t[3]-97][t[4]-97][++v[t[3]-97][t[4]-97][0]]=t[0]-97;

}

for (i=0;s[i];++i) g[i][i]=f[i][i][s[i]-97]=1;

N=i;

}

int main()

{

int i,j,k,l,m,p,q;

Init();

for (l=1;l<N;++l)

for (j=l;j<N;++j)

for (k=i=j-l;k<j;++k)

for (p=0;p<26;++p)

if (f[i][k][p])

for (q=0;q<26;++q)

if (f[k+1][j][q]&&v[p][q][0])

for (g[i][j]=m=1;m<=v[p][q][0];++m) f[i][j][v[p][q][m]]=1;

h[1]=1;

for (j=1;j<N;++j)

{

h[j+1]=j+1;

for (i=0;i<=j;++i)

if (g[i][j]&&h[i]+1<h[j+1]) h[j+1]=h[i]+1;

}

printf("%d",h[N]);

return 0;

}

查看更多回复
提交回复