当前位置: 代码迷 >> 综合 >> poj-3267-The Cow Lexicon-dp
  详细解决方案

poj-3267-The Cow Lexicon-dp

热度:13   发布时间:2023-12-19 11:26:46.0

题意:

给你一个字符串,做为被查字符串。

然后给你一系列的字符串,作为字典。

然你从被查字符串中去除掉字典中含有的字符串,可以是不连续的~~

求:被查字符串最小剩下多少个字符。

做法:

dp[i]代表第i字符后面的字符去除掉字典后剩下几个字符。

dp[i]=min(dp[i],dp[i+1]+1,dp[k+1]+k+1-i-lens);

k代表从第i个字符,往后走,可以找到的一个字典中有的字符串的结束。

lens代表这个字符串的长度。

注意:

dp题目无注意,找好状态方程就好了。

还是有一点需要注意,i后面有可能有好多字符串,所以每比较出来一个字符串,都要min一下。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAXS 999999
using namespace std;
int min(int a,int b,int c)
{// printf("%d %d %d\n",a,b,c);int d=a;if(a>b)d=b;if(d>c)d=c;return d;
}
int main()
{int w,l,i,j,k;char str[1001];char dian[601][30];cin>>w>>l;getchar();gets(str);for(i=0;i<w;i++){gets(dian[i]);}int dp[301];for(i=0;i<301;i++){dp[i]=MAXS;}int lens;dp[l]=0;int x2=0;for(i=l-1;i>=0;i--){for(j=0;j<w;j++){dp[i]=min(dp[i],MAXS,dp[i+1]+1);if(dian[j][0]!=str[i])continue;lens=strlen(dian[j]);x2=0;for(k=i;k<l;k++){if(dian[j][x2]==str[k]){x2++;}if(x2==lens)break;}if(k!=l){dp[i]=min(dp[i],dp[i+1]+1,dp[k+1]+k+1-i-lens);}}//printf("%d %d,%d %d %d\n",j,w,i,k,lens);// printf("dp[%d]=%d\n",i,dp[i]);}printf("%d\n",dp[0]);return 0;
}