2282 - 【基础背包入门3.1】单词的划分
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。
Input
第一行，一个字符串。（字符串的长度不超过100）
第二行一个整数n，表示单词的个数。（n<=100）
第3~n+2行，每行列出一个单词。
Output
一个整数，表示字符串可以被划分成的最少的单词数。
Examples
Input
realityour 5 real reality it your our
Output
2
Solution C++
#include<stdio.h> #include<stdlib.h> #include<string.h> char st[110]; char s[110][110]; bool tf(int x,int y) { for(int i=strlen(s[y])-1;i>=0;i--) if (st[--x]!= s[y][i]) return 0; return 1; } int main() { int n; gets(st); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%s",s[i]); int f[110]; f[0]=0; for(int i=1;i<=strlen(st);i++) { f[i]=100; for(int j=0;j<n;j++) if( strlen(s[j])<=i) if(f[i]>f[i-strlen(s[j])]+1) if(tf(i,j)) f[i]=f[i-strlen(s[j])]+1; } printf("%d\n",f[strlen(st)]); return 0; }