记录编号	410286	评测结果	AAAAAAAAAA
题目名称	[USACO Feb07] 奶牛词典	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2017-05-31 16:27:36	内存使用	1.36 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define sc(a) scanf("%d",&a)
#define for1(a,b,i) for(int i=a;i<=b;i++)
#define for2(a,b,i) for(int i=a;i>=b;i--)
int n,len;
int l[605],wz[605][301],f[301][301];
string s;
string dc[605];
int main()
{
    freopen("lexicon.in","r",stdin);
    freopen("lexicon.out","w",stdout);
    //memset(f,0x3f,sizeof(f));
    sc(n);sc(len);
    cin>>s;
    for1(0,len-1,i)
      for1(i,len-1,j)
         f[i][j]=j-i+1;
    for1(1,n,i){
       int js=0;
       cin>>dc[i];
       l[i]=dc[i].size();
       for1(0,len-1,j)
          if(s[j]==dc[i][0]&&len-j>=l[i]){
              wz[i][++js]=j;
              //cout<<js<<" "<<j<<endl;
          }
       wz[i][0]=js;
    }
    for1(1,n,i){
        for1(1,wz[i][0],j){
          bool pd=false;
          int head=wz[i][j],tail=wz[i][j],js=0;
          while(tail<len){
             if(js==l[i]-1){
                pd=1;
                break;
             }
             tail++;
             if(s[tail]==dc[i][js+1])
                js++;
          }
          if(pd){
             f[head][tail]=min(f[head][tail],tail-head-l[i]+1);
             //cout<<head<<" "<<tail<<" "<<f[head][tail]<<endl;
          }
       }
    }
    for2(len-1,0,i)
       for1(i+1,len-1,j)
          if(f[i][j])
            for1(i,j-1,k)
               f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            // cout<<f[i][j]<<endl;
    printf("%d",f[0][len-1]);
    //while(1);
    return 0;
}