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;
}