题目链接
题目大意：有n个串，要求选出其中的若干个（同一个串可以重复选），堆成一个字符串矩阵，从左上蛇形展开得到一个长串，要求给定的另一个串是这个长串的子序列 最小化使用的串的数量
题解：Orz Claris
我的收获：……
#include <bits/stdc++.h> using namespace std; const int N=225; int n,L,m; char s[N]; bool g[N][N]; bitset<105>f[N][26],tmp,full; inline bool check(int n) { for(int i=1;i<=L;i++) for(int j=1;j<=n;j++) { tmp=full; for(int k=j,o=i;k<=m;k+=n,o++) if(o>L) tmp.reset(); else tmp&=f[o][s[k]]; g[i][j]=tmp.count()>0; } for(int i=1,j;i<=L;i++) { for(j=1;j<=n;j++) if(!g[i][j]) break; if(j>n) return 1; for(;j<=n;j++) if(!g[i+1][j]) break; if(j>n) return 1; } return 0; } void work() { for(int i=1;i<=m;i++) if(check(i)){printf("%d\n",i);return ;} } void init() { scanf("%d%d",&n,&L); for(int i=1;i<=n;i++){ scanf("%s",s+1); full[i]=1; for(int j=1;j<=L;j++) f[j][s[j]-'a'][i]=1; } scanf("%s",s+1);m=strlen(s+1); for(int i=1;i<=m;i++) s[i]-='a'; } int main() { init(); work(); return 0; }