题意:
给你一个字符串,做为被查字符串。
然后给你一系列的字符串,作为字典。
然你从被查字符串中去除掉字典中含有的字符串,可以是不连续的~~
求:被查字符串最小剩下多少个字符。
做法:
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;
}