传送门

题意：

给出一个有n个字符串的匹配串，和m个有k个字符串的文本串，将匹配串进行全排列和文本串进行匹配，找到能全匹配成功的最小的逆序对数

n<=15,m<=10,k<=500000

Solution：

通过哈希+map把字符串变成数字

那么问题就转化成了把一个1到n的序列的全排列和一些序列进行匹配，找到能全匹配成功的最小的逆序对数

一个显然的状压dp状态是能想到的： f[i][j] f [ i ] [ j ] 表示前i位已经匹配了状态为j的数，最小的逆序对数，转移可以通过预处理达到O(n)，但是这样一次的复杂度是 O(k∗2n∗n) O ( k ∗ 2 n ∗ n ) 的，显然复杂度爆炸，但是转移好像不能优化的样子….

所以我们需要换个状态！

我们发现k太大了，但是我们需要的只有n个数，也就是说原状态会有很多没有用的转移

所以我们尝试让状态与n相关

f[i][j] f [ i ] [ j ] 表示产生了i个逆序对，已经匹配了状态为j的数至少需要到文本串的第几位

然后我们再预处理一下辅助数组，就可以实现O(n)转移了

这样的话一次的复杂度是 O(n2∗n∗2n) O ( n 2 ∗ n ∗ 2 n ) ,是非常优秀的

代码：

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
const int bas=211;
const int mod=1315326179;
char s[11];
char c[500010][11];
int n,m,k,ha,len;
int f[150][1<<15];
int num[20];
int go[500010][20];//i项以后最早和原序列第j项匹配的位置 
map<int,int> vis;
int ans=0,pos;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        ha=0;
        for (int j=1;j<=len;j++) ha=(1ll*ha*bas+s[j])%mod;
        vis[ha]=i;
    }
    scanf("%d",&k);
    for (int t=1;t<=k;t++)
    {
        scanf("%d",&m);
        for (int i=1;i<=n;i++) go[m+1][i]=1e9;
        for (int i=1;i<=m;i++) scanf("%s",c[i]+1);
        for (int i=m;i>=1;i--)
        {
            for (int j=1;j<=n;j++) go[i][j]=go[i+1][j];
            len=strlen(c[i]+1);
            ha=0;
            for (int j=1;j<=len;j++) ha=(1ll*ha*bas+c[i][j])%mod;
            int nw=vis[ha];
            if (nw) go[i][nw]=i;
        }
        bool pan=0;
        for (int i=1;i<=n;i++) {go[0][i]=go[1][i];if (go[0][i]==1e9) {pan=1;break;}}
        if (pan) continue;
        memset(f,63,sizeof(f));
        f[0][0]=0;
        for (int i=0;i<=n*(n-1)/2;i++)
        {
            if (i&&f[i-1][(1<<n)-1]<1e9) break;
            for (int j=0;j<(1<<n);j++)
                if (f[i][j]<1e9)
                {
                    if (j==((1<<n)-1)) {
  if (ans<n*(n-1)/2-i+1) pos=t,ans=n*(n-1)/2-i+1;break;}
                    for (int l=1;l<=n;l++) num[l]=num[l-1]+((j>>(l-1))&1);
                    for (int p=1;p<=n;p++)
                        if (!(1&(j>>(p-1))))
                            f[i+num[n]-num[p]][j|(1<<p-1)]=min(f[i+num[n]-num[p]][j|(1<<p-1)],go[f[i][j]][p]);
                }
        }
    }
    if (ans==0) printf("Brand new problem!");
    else {
  printf("%d\n",pos);printf("[:");for (int i=1;i<=ans;i++) printf("|");printf(":]");}
}