http://acm.pku.edu.cn/JudgeOnline/problem?id=3267
dp题
f[i]=min{match[j+1,i]+f[j]};
具体做的时候，对于每个f[i],检查所有长度<=i的单词，然后把该单词与
目标单词从后往前比较找出用该单词匹配时要去掉的字母数，在状态转移
方程f[i]=min{f[j+1,i]+f[j]}中的中间点j就是最后一趟比较完之后目标
单词向前滑动最远处。然后f[i]取所有单词中最小的一个.
Source Code
| Problem: 3267 |
|
User: lovecanon |
| Memory: 256K |
|
Time: 141MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char word[301],dict[601][26];
int f[301],len[601];
int main(){
int i,j,length,tot,minlen=1000;
scanf("%d%d",&tot,&length);getchar();
for(i=1;i<=length;i++) word[i]=getchar();
for(i=1;i<=tot;i++) {
scanf("%s",dict[i]);
if((len[i]=(int)strlen(dict[i]))<minlen) minlen=len[i];//先求出各个单词的长度
}
memset(f,0,sizeof(f));
f[0]=0;
for(i=1;i<minlen;i++) f[i]=i;//预处理
for(i=minlen;i<=length;i++){
int min=i;//注意初值要赋值为i
for(j=1;j<=tot;j++){
int ind1=i,ind2=len[j]-1,sum=0;//id1是目标单词的位置，id2是单词表中单词的位置
if(ind2>i) continue;//如果取出的单词长于目标单词，显然不行
while(ind1>0&&ind2>=0){
if(word[ind1]==dict[j][ind2]) {ind1--;ind2--;}//如相等,都向前滑动
else{
sum++;//否则，目标单词向前滑，sum++
ind1--;
}
}
if(ind2<0&&(sum=sum+f[ind1])<min) min=sum;//如果最后索取出的单词的字母全部匹配上，
} //且sum+f[ind1])<min，则更新
f[i]=min;
}
printf("%d\n",f[length]);
system("pause");
return 0;
}