題意： 給你一個字符串，做為被查字符串。 然後給你一系列的字符串，作為字典。 然你從被查字符串中去除掉字典中含有的字符串，可以是不連續的~~ 求：被查字符串最小剩下多少個字符。 做法： 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一下。 [html] #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; }
