http://acm.pku.edu.cn/JudgeOnline/problem?id=3267
dp題
f[i]=min{match[j+1,i]+f[j]};
具體做的時(shí)候，對于每個(gè)f[i],檢查所有長度<=i的單詞，然后把該單詞與
目標(biāo)單詞從后往前比較找出用該單詞匹配時(shí)要去掉的字母數(shù)，在狀態(tài)轉(zhuǎn)移
方程f[i]=min{f[j+1,i]+f[j]}中的中間點(diǎn)j就是最后一趟比較完之后目標(biāo)
單詞向前滑動最遠(yuǎn)處。然后f[i]取所有單詞中最小的一個(gè).
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];//先求出各個(gè)單詞的長度
}
memset(f,0,sizeof(f));
f[0]=0;
for(i=1;i<minlen;i++) f[i]=i;//預(yù)處理
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是目標(biāo)單詞的位置，id2是單詞表中單詞的位置
if(ind2>i) continue;//如果取出的單詞長于目標(biāo)單詞，顯然不行
while(ind1>0&&ind2>=0){
if(word[ind1]==dict[j][ind2]) {ind1--;ind2--;}//如相等,都向前滑動
else{
sum++;//否則，目標(biāo)單詞向前滑，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;
}