先用KMP求出所有可以放的位置，然后两个值分别处理。
最大值：
贪心，4!枚举放的先后位置顺序，2^3枚举相邻两个串是否有交。
若有交，则后一个的起始位置一定是离前一个的结束位置最近的位置，无交也一样。
最小值：
首先去掉被其它串包含的串，因为肯定可以和其它串放同样的位置。
将所有串从长到短排序方便DP。
f[S][i]表示当前放的串的情况为S，串目前所覆盖到的最后一个位置为i，覆盖的最小总长度是多少，则有：
当最后一个覆盖到i的串位置与其它串不相交时：f[S][i]=min{f[S'][k]} 这个用一个前缀和优化即可。
当相交时：f[S][i]=min(f[S'][j]+i-j) 因为串已经从长到短排好序了所有没有问题。这个用单调队列优化即可。
写的龟速，跑得飞快。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define mem(a) memset(a,0,sizeof(a)) 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 using namespace std; 7 8 const int N=10010; 9 char s[5][N],A[N]; 10 bool b[5],fl[5][N]; 11 int T,n,len,L[5],pos[5][N],num[5],nxt[N],p[5],st[20],ed[20],f[20][N],g[20][N],q[20][N]; 12 13 void KMP(char S[],char T[],int pos[],int &num,bool fl[]){ 14 int n=strlen(T+1),m=strlen(S+1),j=0; nxt[1]=0; 15 rep(i,2,m){ 16 while (j && S[j+1]!=S[i]) j=nxt[j]; 17 if (S[j+1]==S[i]) nxt[i]=++j; else nxt[i]=0; 18 } 19 j=0; num=0; 20 rep(i,1,n){ 21 while (j && S[j+1]!=T[i]) j=nxt[j]; 22 if (S[j+1]==T[i]) j++; 23 if (j==m) pos[++num]=i-m+1,fl[i]=1,j=nxt[j]; 24 } 25 } 26 27 bool chk(char S[],char T[]){ 28 int n=strlen(T+1),m=strlen(S+1); 29 rep(i,1,n-m+1){ 30 bool flag=0; 31 rep(j,1,m) if (S[j]!=T[i+j-1]){ flag=1; break; } 32 if (!flag) return 1; 33 } 34 return 0; 35 } 36 37 void solve_max(){ 38 rep(i,1,n) p[i]=i; int ans=0; mem(fl); 39 do{ 40 for (int S=0; S<1<<(n-1); S++){ 41 int x=pos[p[1]][1]+L[p[1]]-1,res=L[p[1]]; ans=max(ans,res); bool flag=0; 42 rep(i,2,n){ 43 int d=upper_bound(pos[p[i]]+1,pos[p[i]]+num[p[i]]+1,x)-pos[p[i]]; 44 if (S&(1<<(i-2))){ 45 if (d<=num[p[i]] && pos[p[i]][d]>x) res+=L[p[i]],x=pos[p[i]][d]+L[p[i]]-1; 46 else{ flag=1; break; } 47 }else{ 48 d--; 49 if (d && pos[p[i]][d]<=x) res+=L[p[i]]-(x-pos[p[i]][d]+1),x=pos[p[i]][d]+L[p[i]]-1; 50 else{ flag=1; break; } 51 } 52 if (!flag) ans=max(ans,res); 53 } 54 } 55 }while (next_permutation(p+1,p+n+1)); 56 printf("%d ",ans); 57 } 58 59 void solve_min(){ 60 int S0=(1<<n)-1; 61 rep(i,1,n-1) rep(j,i+1,n) if (!b[j] && chk(s[j],s[i])) b[j]=1,S0^=1<<(j-1); 62 memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g)); 63 mem(f[0]); mem(g[0]); 64 rep(i,0,(1<<n)-1) st[i]=1,ed[i]=0; 65 rep(i,1,len){ 66 for (int S=1; S<1<<n; S++){ 67 if (S&(S^S0)) continue; g[S][i]=g[S][i-1]; 68 rep(j,1,n) if (S&(1<<(j-1)) && fl[j][i]){ 69 int S1=S^(1<<(j-1)); 70 if (i-L[j]>=0) f[S][i]=min(f[S][i],g[S1][i-L[j]]+L[j]); 71 while (st[S1]<=ed[S1] && q[S1][st[S1]]<=i-L[j]) st[S1]++; 72 if (st[S1]<=ed[S1]) f[S][i]=min(f[S][i],f[S1][q[S1][st[S1]]]+i-q[S1][st[S1]]); 73 while (st[S]<=ed[S] && f[S][q[S][ed[S]]]-q[S][ed[S]]>=f[S][i]-i) ed[S]--; 74 q[S][++ed[S]]=i; g[S][i]=min(g[S][i-1],f[S][i]); 75 } 76 } 77 } 78 printf("%d ",g[S0][len]); 79 } 80 81 int main(){ 82 freopen("bzoj4560.in","r",stdin); 83 freopen("bzoj4560.out","w",stdout); 84 for (scanf("%d",&T); T--; ){ 85 mem(fl); mem(b); scanf("%s",A+1); len=strlen(A+1); scanf("%d",&n); 86 rep(i,1,n) scanf("%s",s[i]+1),L[i]=strlen(s[i]+1); 87 rep(i,1,n-1) rep(j,i+1,n) if (L[i]<L[j]) swap(s[i],s[j]),swap(L[i],L[j]); 88 rep(i,1,n) KMP(s[i],A,pos[i],num[i],fl[i]); 89 solve_min(); solve_max(); 90 } 91 return 0; 92 }