这道题与CCC的zuma异曲同工,只是求不同的东西,一开始我想直接用o(L^3*S*P)结果发现有20亿,好像过不了,没想到常数这么小,竟然就是标解了
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int ans[200],f[200][200],g[200][50][50],len,n,b[200]; char ch[200],c[50][200]; void init() { scanf("%s\n",ch+1); len=strlen(ch+1); scanf("%d\n",&n); for (int i=1;i<=n;i++) { scanf("%s\n",c[i]+1); b[i]=strlen(c[i]+1); } } void dfs(int x,int y,int z,int s) { g[x][y][z]=s; if (z==b[y]) { if (!f[s][x]) for (int i=x+1;i<=len;i++) if (f[x+1][i]) f[s][i]=1; f[s][x]=1; return ; } for (int i=x+1;i<=len;i++) if (f[x+1][i-1] && c[y][z+1]==ch[i] && g[i][y][z+1]!=s) dfs(i,y,z+1,s); } void cherry(int s) { for (int i=s;i<=len;i++) if (f[s][i-1]) for (int j=1;j<=n;j++) if (c[j][1]==ch[i]) dfs(i,j,1,s); } int main() { freopen("A.in","r",stdin); freopen("A.out","w",stdout); init(); memset(f,0,sizeof(f)); int i,j; for (i=1;i<=len;i++) f[i][i-1]=1; for (i=len;i>=1;i--) cherry(i); memset(ans,61,sizeof(ans)); ans[0]=0; for (i=1;i<=len;i++) { for (j=0;j<=i-1;j++) if (f[j+1][i]) ans[i]=min(ans[i],ans[j]); else ans[i]=min(ans[i],ans[j]+i-j); ans[len+1]=min(ans[len+1],ans[i]+len-i); } printf("%d\n",ans[len+1]); return 0; }