P2031 脑力达人之分割字串
字符串dp，f[i]表示主串到第i个字符，最多能分割成多少子串。
f[i]=max(f[i],f[k]+1);k是能匹配到的前一位。
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 #include<cmath> 6 #include<ctime> 7 #include<set> 8 #include<map> 9 #include<stack>10 #include<cstring>11 #define inf 214748364712 #define For(i,a,b) for(register int i=a;i<=b;i++)13 #define p(a) putchar(a)14 #define g() getchar()15 //by war16 //.10.2917 using namespace std;18 char a[310],c[521][310];19 int n;20 int la,lb;21 bool flag;22 int f[310];23 int mx;24 void in(int &x)25 {26int y=1;27char c=g();x=0;28while(c<'0'||c>'9')29{30if(c=='-')31y=-1;32c=g();33}34while(c<='9'&&c>='0')x=x*10+c-'0',c=g();35x*=y;36 }37 void o(int x)38 {39if(x<0)40{41 p('-');42 x=-x;43}44if(x>9)o(x/10);45p(x%10+'0');46 }47 int main()48 {49cin>>(a+1);50la=strlen(a+1);51in(n);52For(i,1,n)53cin>>(c[i]+1);54For(i,1,la)55{56 f[i]=mx;57 For(j,1,n)58 {59 flag=false;60 lb=strlen(c[j]+1);61 if(lb<=i)62 {63 For(k,1,lb)64 if(a[i-lb+k]!=c[j][k])65 {66 flag=true;67 break;68 }69 if(!flag)70 f[i]=max(f[i],f[i-lb]+1);71 }72 }73 if(f[i]>mx)74 mx=f[i];75}76o(f[la]);77return 0;78 }
