【BZOJ4560】[JLoi2016]字符串覆盖

Description

字符串A有N个子串B1,B2,…,Bn。如果将这n个子串分别放在恰好一个它在A中出现的位置上（子串之间可以重叠）这样A中的若干字符就被这N个子串覆盖了。问A中能被覆盖字符个数的最小值和最大值。

Input

第一行包含一个正整数T，表示数据组数。保证T≤10。接下来依次描述T组数据，每组数据中：第一行包含一个由小写字母组成的字符串，表示母串A。第二行包含一个整数N，表示子串的个数。接下来N行，每行包含一个由小写字母组成的字符串，描述子串。数据保证所有子串均在母串中出现。字符串长度A<=10000,N<=4,子串长充<=1000

Output

输出为T行，对应每组数据的答案。每行包含两个整数Minans和Maxans，分别表示对应数据中能被覆盖字符数量的最小值和最大值。

Sample Input

2

hello

4

he

l

l

o

abacaba

4

ab

ba

a

c

Sample Output

4 5

4 6

题解：网上题解说是某贪心？然而我只会状压DP。

先用KMP求出每个子串的所有出现位置，然后用f[i][j]表示前i个字符，子串的出现情况为j的覆盖数量最大值，g[i][j]表示最小值。转移时需要用到树状数组。

然而状压的做法似乎好多情况都无法处理，如子串存在包含的情况。。。总之加了一坨特判就过了，可能会被hack。

代码不可读。

 

#include 
     
      #include 
      
       #include 
       
        #define lson x<<1#define rson x<<1|1using namespace std;const int maxn=10010;int n,m;int len[5],vis[5],ch[maxn],next[maxn];char S[maxn],T[5][maxn];int f[maxn][16],g[maxn][16],sf[maxn][16],sg[maxn][16];struct node{	int s[maxn],typ;	inline int cmp(int a,int b)	{		return ((a>b)^typ)?a:b;	}	inline void updata(int x,int v)	{		x++;		for(int i=x;i;i-=i&-i)	s[i]=cmp(s[i],v);	}	inline int query(int x)	{		x++;		int i,ret=s[0];		for(i=x;i<=m+1;i+=i&-i)	ret=cmp(ret,s[i]);		return ret;	}}s1[16],s2[16];void work(){	scanf("%s",S),m=strlen(S);	scanf("%d",&n);	int i,j,k,a,b,tmp=(1<
        
         >(k-1))&1)&&((ch[i]>>(k-1))&1))			{				s1[j|(1<<(k-1))].updata(i+len[k],f[i][j]-i);				sf[i+len[k]][j|(1<<(k-1))]=max(sf[i+len[k]][j|(1<<(k-1))],f[i][j]+len[k]);				if(!vis[k])				{					s2[j|(1<<(k-1))].updata(i+len[k],g[i][j]-i);					sg[i+len[k]][j|(1<<(k-1))]=min(sg[i+len[k]][j|(1<<(k-1))],g[i][j]+len[k]);				}			}		}	}	int ans=0;	for(i=1;i<1<