infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
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;
}




posted on 2008-11-01 21:56 infinity 阅读(335) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理