首页 > 代码库 > poj3267（The Cow Lexicon）
poj3267（The Cow Lexicon）
题目地址：The Cow Lexicon
题目大意：
奶牛有自己的识别单词的语言，它有自己的字典序列，如果给一串字符不符合奶牛的字典里的单词，奶牛就无法识别，你的任务就是找出给的字符串中包含给出奶牛字典的单词，至少从主串里删除几个字符，使主串只包含奶牛字典里的单词，不包含多于的字符。
解题思路：
动态规划ｄｐ。 ＤＰ一直都不太懂，不看解题报告根本推不出来状态方程，入门水平都不够，需要好好练习学习该知识点。
状态方程： dp[i] i 代表从i到L最少需要删除的字符个数。
首先分为两种思想：
一是不能匹配成功 ： dp[i]=dp[i+1]+1；（从后往前推）
二是匹配成功： dp[i]=min（dp[i]，dp[p1+1]+p1+1-i-len）；
解释一下第二个式子:
dp[p1+1]+p1+1-i-len. 因为能够匹配成功，从字符串数组 i 开始匹配，p1代表和字典字符串匹配结束位于主串的位置。 p1+1-i 代表主串用了多少个字符与字典字符串匹配成功。然后-len 代表需要删除的字符个数，然后 + dp[p1+1] 意为加上从p1+1位置到L的最小删除的个数。 所以整个式子代表dp[i]匹配成功时最少删除的个数。 因为从主串 i 位置到p1位置可能匹配很多次奶牛字典字符串，这时我们应该选取较小的dp[i]。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 #include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 #define PI 3.141592721 /***************************************/22 const int INF = 0x7f7f7f7f;23 const double eps = 1e-8;24 const double PIE=acos(-1.0);25 const int d1x[]= {0,-1,0,1};26 const int d1y[]= {-1,0,1,0};27 const int d2x[]= {0,-1,0,1};28 const int d2y[]= {1,0,-1,0};29 const int fx[]= {-1,-1,-1,0,0,1,1,1};30 const int fy[]= {-1,0,1,-1,1,-1,0,1};31 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/32 /***************************************/33 void openfile()34 {35 freopen("data.in","rb",stdin);36 freopen("data.out","wb",stdout);37 }38 priority_queue<int> qi1;39 priority_queue<int, vector<int>, greater<int> >qi2;40 /**********************华丽丽的分割线,以上为模板部分*****************/41 int min(int a,int b)42 {43 if (a<b)44 return a;45 return b;46 }47 int main()48 {49 int n,m;50 while(scanf("%d%d",&m,&n)!=EOF)51 {52 char s1[305],s2[605][305];53 int dp[305];54 memset(s1,0,sizeof(s1));55 memset(s2,0,sizeof(s2));56 memset(dp,0,sizeof(dp));57 int i,j;58 scanf("%s",s1);59 for(i=0; i<m; i++)60 scanf("%s",s2[i]);61 int len1=strlen(s1);62 dp[len1]=0;63 for(i=len1-1; i>=0; i--)64 {65 dp[i]=dp[i+1]+1;66 for(j=0; j<m; j++)67 {68 int len2=strlen(s2[j]);69 int p1=i;70 int p2=0;71 while(len1-i>=len2&&s1[i]==s2[j][0])72 {73 if (s1[p1++]==s2[j][p2])74 {75 p2++;76 }77 if (p2==len2)78 {79 dp[i]=min(dp[i],dp[p1]+p1-i-len2); //这里没有p1+1，原因：p1++；80 break;81 }82 if(p1>=len1)83 break;84 85 }86 }87 }88 printf("%d\n",dp[0]);89 }90 return 0;91 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。