首页 > 代码库 > POJ 3267

POJ 3267

2024-07-07 20:11:56   222人阅读

dp经典

关于这道题，我看了网上大量的资料，发现整体思路是对的，但是细节解释是错的(或者说不到位)

Len = strlen(say);  say是牛说的话，下面的word代表单词列表

dp[i]表示从say中第i个字符开始，到第Len-1个字符（结尾处）这段区间所删除的字符数，初始化为dp[i]=len-i;

从say尾部到头部扫描，会方便一点；

递推式：

dp[i] = dp[i+1] + 1;（不能匹配时，最坏情况删除最多字符）

dp[i] = min( dp[i], dp[dt]+dt-i-tmp ); (能匹配，选取最优)

tmp指向单词，dt指向say

关键就是这两个递推式了，好好解释一下：

匹配的过程是：

当确认say第i位和某单词的首位吻合时，就开始逐字匹配，字符相同则两个指针同时向后移动一次，否则tmp固定，dt移动。当因为dt>=L(从下标0开始)跳出匹配时，说明匹配失败，dp[i]状态不变；当tmp==单词长度len时，单词匹配成功，进行dp[i]的状态优化

需要强调的是，这里要把w个单词中的每一个都去尝试匹配一下，在所有尝试开始之前把dp[i] 设为 dp[i+1] + 1；(可以看出dp[i]的初始化是没有必要的，只要将dp[len]设为0就可以了)

在每次匹配成功后进行dp[i]的优化，最后的答案就是dp[0]啦！

 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 #include<math.h>
 6 #include<algorithm>
 7 #include<string.h>
 8 #include<stdlib.h>
 9 #include<vector>
10 #include<set>
11 #include<map>
12 #include<stack>
13 #include<string>
14 #include<queue>
15 
16 #define repA(p,q,i)  for( int (i)=(p); (i)!=(q); ++(i) )
17 #define repAE(p,q,i)  for( int (i)=(p); (i)<=(q); ++(i) )
18 #define repD(p,q,i)  for( int (i)=(p); (i)!=(q); --(i) )
19 #define repDE(p,q,i)  for( int (i)=(p); (i)>=(q); --(i) )
20 
21 char words[610][30];
22 char say[310];
23 int dp[310];
24 
25 int main()
26 {
27     int w,len;
28     while( scanf("%d%d", &w, &len) != EOF )
29     {
30            scanf("%s", say);
31            repA(0, w, i)
32              scanf("%s", &words[i][0]);
33            int dt;
34            repAE(0, len, i)
35              dp[i] = len - i;
36            bool flag;
37            int tmp;
38            
39            repDE(len-1, 0, i)
40            {
41                    dp[i] = dp[i+1] + 1;
42                    repA(0, w, j)
43                    {
44                            flag = false;
45                            if(say[i] != words[j][0])  continue;
46                            dt = i;
47                            tmp = 0;
48                            while(dt < len)
49                            {  
50                                 if( words[j][tmp] == say[dt] )
51                                 {  ++dt;  ++tmp;  }
52                                 else ++dt;
53                                 
54                                 if(words[j][tmp] == ‘\0‘)
55                                 {  flag = true;  break;  }
56                            }
57                            
58                            if(flag) dp[i] = min( dp[i], dp[dt]+dt-i-tmp );       
59                    } 
60                    
61                                      
62            }
63            
64            printf("%d\n", dp[0]);
65 
66     }    
67 }
View Code

 

 


联系
我们