题解 P3269 【[JLOI2016]字符串覆盖】

kczno1 · 2017-02-18 17:14:16 · 题解

n<=4，n!枚举放置顺序。

最大值:

要尽量少交。

第一个串应该放的尽量前面。

第二个串开头如果跟第一个串不交，应该放在尽量前面；

如果跟第一个串交，应该放在尽量后面，因为如果把前两个串看作一个整体，这样会最长。

后面也一样。

最小值:

第一个串如果不选择第一个位置放，就是一个2->l,1->n的子问题。

如果选择第一个位置放，

如果第二个串不交第一个串，就是末尾+1->l,2->n的一个子问题。

否则第二个串应该放的尽量前面，因为如果把前两个串看作一个整体，这样会最短。

后面的也一样。

dp,状态数O(nl)，转移O(1)。

#include<bits/stdc++.h>
using namespace std;

void chmax(int &x,int y) { if(x<y)x=y; }
void chmin(int &x,int y) { if(x>y)x=y; }
#define N 5
#define L 10005
char s[L];int l;
char q[1003];int m;
int pre[N][L],next[N][L],len[N],n;//pre:<=第一个开头匹配 next:>=第一个开头匹配 
int id[N],*pr[N],*nex[N],le[N];
int fail[L],i,j;
void init()
{
    for (i=2;i<=m;++i)
    {
        char now=q[i];
        j=fail[i-1];
        while (j&&q[j+1]!=now) j=fail[j];
        fail[i]=(q[j+1]==now)?j+1:0;
    }
}

bool mark[L];
void ins(int *pre,int *next)
{
    i=0;
    for (j=1;j<=l;++j)
    {
        char now=s[j];
        while (i&&q[i+1]!=now) i=fail[i];
        if (q[i+1]==now) 
        {
            ++i;
            if (i==m) mark[j-m+1]=1;
        }
    }
    for (i=1;i<=l;++i) pre[i]=mark[i]?i:pre[i-1];
    pre[i]=pre[i-1];
    next[l+1]=0;
    for (i=l;i;--i) 
    if (mark[i]) {next[i]=i;mark[i]=0;}
    else next[i]=next[i+1];
}

int f[L][N];bool vis[L][N];
bool *st[N*L];int top;
int dp(int first,int num)//first:字符串=[first..l] num:第几个子串   
{
    if (num>n) return 0;
    first=nex[num][first];
    int &ans=f[first][num];
    if (*(st[top+1]=&vis[first][num])) return ans;*st[++top]=1;
    ans=dp(first+1,num); 
    int last=first+le[num],x0=first;//x0是num-1的开头 
    while ((++num)<=n)
    {
        chmin(ans,dp(last,num)+last-first);//第num个选择不交 
        int x=nex[num][first];
        if (x<x0||x>=last) return ans;
        x0=x;
        chmax(last,x+le[num]);//选择交
    }
    chmin(ans,last-first);
    return ans;
}

int get(int first,int num)
{
    if (num>n) return 0;
    first=nex[num][first];
    if(!first) return -L;
    int last=first+le[num],x0=first,ans=-L;
    while ((++num)<=n)
    {
      chmax(ans,get(last,num)+last-first); //不交 
      int x=pr[num][last];//交:尽量后面 
      if (x<x0||x>=last) return ans;
      x0=x;
      chmax(last,x+le[num]);
    }
    return max(ans,last-first);
} 

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    for (i=1;i<=4;++i) { vis[0][i]=1;f[0][i]=L; }
    int tt,i,j;scanf("%d",&tt);
    while (tt--)
    {
        scanf("%s",s+1);l=strlen(s+1);
        scanf("%d",&n);
        for (i=1;i<=n;++i) 
        {
            scanf("%s",q+1);len[i]=m=strlen(q+1);
            init();
            ins(pre[i],next[i]);
        }
        for (i=1;i<=n;++i) id[i]=i;
        int ans1=L,ans2=0;
        do
        {
            for (i=1;i<=n;++i) {pr[i]=pre[id[i]];nex[i]=next[id[i]];le[i]=len[id[i]];}
            chmin(ans1,dp(1,1));
            for (;top;--top) *st[top]=0;
            chmax(ans2,get(1,1));
        }while (next_permutation(id+1,id+n+1));
        printf("%d %d\n",ans1,ans2);
    }
}