巢穴

about:blank

P3267

动态规划

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int w,l;
string message;
string ch[601];
int f[301];
int main()
{
 cin>>w>>l;
 cin>>message;
 for (int i=0;i<w;i++)
  cin>>ch[i];
 memset(f,0,sizeof(f));
 for (int i=0;i<l;i++)
  f[i]=1000000;
 
 for (int i=l-1;i>=0;i--)
 {
  int min_=1000000;
  for (int j=0;j<w;j++)
  {
   
   int pos=i,p=0;
   while(pos<l)
   {
    if (message[pos]==ch[j][p]) p++;
    pos++;
    if (p==ch[j].length()) break;
   }
   if (p==ch[j].length())
   {
    for (int k=pos;k<=l;k++)
    {
     if (min_>k-i-ch[j].length()+f[k]) min_=k-i-ch[j].length()+f[k];
    }
   } 
  }
  f[i]=min_;
 }
 cout<<f[0]<<endl;
 system("pause");
    
 return 0;
}

posted on 2009-11-05 16:10 Vincent 阅读(117) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理