题目
题解
对于求最大值的情况，如果确定子串出现顺序的话，贪心即可，即最优情况把当前串放在上一个串结尾后面第一个出现位置，否则放在上一个串结尾前面第一个出现位置
对于求最小值的情况，设$f_{i,j}$表示转移到低$i$个字符子串出现状态为$j$（去重后）的最小值，设当前串为$S$，则有式子$f_{i,j}=\min(f_{a,j-S},f_{b,j-S}),i-len_S+1\le a\le i,1\le b\le i-len_S$
直接线段树维护即可其实可以单调队列
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=1e4+5,inf=1e9;
struct p{
int x,x_;
}s[16][MAX<<2];
int T,n,N,cnt,mx;
int nxt[MAX],pos[MAX<<2],len[4],id[4],re[4];
char a[MAX],b[MAX];
bool use[4];
vector<int> vec[4],Vec[MAX];
void GET_NXT(int n)
{
int k=0;
memset(nxt,0,sizeof(nxt));
for(int i=2;i<=n;++i)
{
while(k>0&&b[k+1]!=b[i]) k=nxt[k];
if(b[k+1]==b[i]) ++k;
nxt[i]=k;
}
}
void KMP(int id,int m)
{
int k=0;
for(int i=1;i<=n;++i)
{
while(k>0&&b[k+1]!=a[i]) k=nxt[k];
if(b[k+1]==a[i]) ++k;
if(k==m)
vec[id].push_back(pos[++cnt]=((i=i-m+1)+m-1)),Vec[pos[cnt]].push_back(id),k=0;
}
}
void pus(int k,p *s) {s[k].x=min(s[tl].x,s[tr].x),s[k].x_=min(s[tl].x_,s[tr].x_);}
void change(int l,int r,int k,int x,int d,p *s)
{
if(l==r) return void(s[k].x=d);
if(x<=mid) change(l,mid,tl,x,d,s);
else change(mid+1,r,tr,x,d,s);
pus(k,s);
}
void change_(int l,int r,int k,int x,int d,p *s)
{
if(l==r) return void(s[k].x_=d);
if(x<=mid) change_(l,mid,tl,x,d,s);
else change_(mid+1,r,tr,x,d,s);
pus(k,s);
}
int ask(int l,int r,int k,int L,int R,p *s)
{
if(r<L||R<l) return 1e9;
if(l>=L&&r<=R) return s[k].x;
return min(ask(l,mid,tl,L,R,s),ask(mid+1,r,tr,L,R,s));
}
int ask_(int l,int r,int k,int L,int R,p *s)
{
if(r<L||R<l) return 1e9;
if(l>=L&&r<=R) return s[k].x_;
return min(ask_(l,mid,tl,L,R,s),ask_(mid+1,r,tr,L,R,s));
}
int look(int x,int id)
{
int l=0,r=vec[id].size()-1,ans=-1;
while(l<=r)
{
if(vec[id][mid]-len[id]+1>x) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int look1(int x,int id)
{
int l=0,r=vec[id].size()-1,ans=-1;
while(l<=r)
{
if(vec[id][mid]-len[id]+1<=x) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int solve()
{
int ans=0;
for(int i=0,x=0,l,r;i<N;++i)
if(!x) x=vec[id[i]][0],ans=len[id[i]];
else
{
r=look(x,id[i]);
if(r!=-1) x=vec[id[i]][r],ans+=len[id[i]];
else l=look1(x,id[i]),ans+=max(vec[id[i]][l]-x,0),x=max(x,vec[id[i]][l]);
}
return ans;
}
void dfs(int x=1)
{
if(x==N+1) return void(mx=max(mx,solve()));
for(int i=0;i<N;++i)
if(!use[i]) use[i]=1,id[x-1]=i,dfs(x+1),use[i]=0;
}
void Solve() {return void(dfs());}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s%d",a+1,&N),n=strlen(a+1),mx=0,cnt=0;
memset(s,127,sizeof(s));
memset(use,0,sizeof(use));
memset(vec,0,sizeof(vec));
memset(Vec,0,sizeof(Vec));
for(int i=0;i<N;++i)
scanf("%s",b+1),GET_NXT(len[i]=strlen(b+1)),KMP(i,len[i]);
Solve();
int M=N,o=0;
for(int i=0;i<N;++i)
{
bool fl=0;
for(int j=0;j<N&&!fl;++j)
if(i!=j&&len[i]<len[j]) for(int k:vec[i])
if(k<=vec[j][0]&&k-len[i]+1>=vec[j][0]-len[j]+1) {--M,fl=1;break;}
if(!fl) id[o]=i,re[i]=o++,use[i]=1;
}
for(int i=0;i<M;++i)
for(int v:vec[id[i]])
change(1,n,1,v,len[id[i]],s[1<<i]),change_(1,n,1,v,len[id[i]]-v,s[1<<i]);
sort(pos+1,pos+1+cnt),cnt=unique(pos+1,pos+1+cnt)-pos-1;
for(int i=0;i<(1<<M);++i)
for(int j=1,x;j<=cnt;++j)
{
x=1e9;
for(int v:Vec[pos[j]])
if(use[v]&&(i&(1<<re[v]))&&i>(1<<re[v]))
x=min(x,min(ask_(1,n,1,pos[j]-len[v]+1,pos[j],s[i-(1<<re[v])])+pos[j],ask(1,n,1,1,pos[j]-len[v],s[i-(1<<re[v])])+len[v]));
if(x<1e9) change(1,n,1,pos[j],x,s[i]),change_(1,n,1,pos[j],x-pos[j],s[i]);
}
printf("%d %d\n",s[(1<<M)-1][1].x,mx);
}
return 0;
}
