题目背景
好吧，该来的废话还是要来的。
画外音：
终于，在两轮的重重选拔之后，我们的海选终于结束了。现在进入我们的循环赛环节。循坏赛一共有四场，最后选出得分最高的16人进入对决，得分相同则和按用时排名，若仍有不能确定16人的情况，则去尾处理。
欢迎您收看有洛谷卫视重磅推出的综合性文艺知识类节目“开心玩游戏，轻松赢比赛”，我是LUWM。学编程，就选洛谷， 感谢洛谷Online Judge对本节目的大力支持。下面，我们有请10位选手上台，由大屏幕给出题目。
题目描述
现在有一个字符串，你可以对这个字符串进行拆分，如abcvsdaas可以拆分为abc|vs|d|aasa，现在再给你一个字典，要求分割成的每一个子串必须要有包含其中的任意一个单词。那么最多可以分为几个子串呢？
输入输出格式
输入格式：第一行，一行字符串
第二行一个数N，表示字典中字符串的数量
接下来N行，每行一个字符串，表示字典中的一个字符串。
输出格式：
一个数，最多的分割数。
输入输出样例
输入样例#1：asdsd3assdds
输出样例#1：
2
说明
特殊情况：
如果原字符串不能被分割，请输出0
数据范围：
对于20%的数据，1<=len(s)<=50,1<=n<=50
对于100%的数据，1<=len(Ai)<=len(s)<=300，1<=N<=500
~~~~~~~~~~~~~~~~~~~~~~~~~~~
trie树+DP~
普及-的题……
对字典建trie树，然后DP~
#include<cstdio>#include<cstring>#include<iostream>using namespace std;int n,m,c[150001][26],cnt,num[150001],f[150001],ans;char s[301],ch[301];void init(){int l=strlen(ch),now=1;for(int i=0;i<l;i++){if(!c[now][ch[i]-'a']) c[now][ch[i]-'a']=++cnt;now=c[now][ch[i]-'a'];}num[now]++;}int main(){scanf("%s%d",s+1,&m);n=strlen(s+1);cnt=1;while(m--){scanf("%s",ch);init();}for(int i=1;i<=n;i++){f[i]=max(f[i],f[i-1]);int now=1,x=i;while(now){now=c[now][s[x]-'a'];if(num[now]) f[x]=max(f[x],f[i-1]+1);x++;}ans=max(ans,f[i]);}printf("%d\n",ans);return 0;}
