自动搬运

查看原文

来自洛谷，原作者为

	chen_03 AFO | 垫底人，啥都不会 | 谁能赐予我一个脑子？ | Brute force 出不了奇迹。

搬运于2025-08-24 21:51:35，当前版本为作者最后更新于2022-03-15 17:07:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于方向相同的两个提示 $x,y$，我们考虑如果 $y$ 能接在 $x$ 的第 $i$ 位之后，应当满足什么条件：

• $x,y$ 作为集合时，$y\subseteq x$；
• $x$ 从第 $i$ 位开始往后的部分（包括第 $i$ 位）是 $y$ 的子序列。

如果我们按这个方向依次填数，若已经填到了 $x$ 的第 $i$ 位，那么我们可以选择停止考虑 $x$，转而考虑 $y$。

若 $i$ 满足条件，则 $i+1$ 也满足条件。我们可以对于每对 $(x,y)$ 预处理出这个最小的 $i$，或者发现不存在这样的 $i$。

（以下所有下标均从 $0$ 开始。记 $a_{i,l}$ 表示提示 $i$ 的第 $l$ 位；$p_{i,l}$ 表示数字 $l$ 在提示 $i$ 中的出现位置，若没有出现则为 $+\infty$；$L_i$ 表示提示 $i$ 的长度）

考虑如果只能往右走怎么做。我们从左到右依次填数。考虑 DP，设 $f(S,i,l)$ 表示已经考虑了集合 $S$ 中的提示，当前正在考虑提示 $i$，已经填了 $i$ 的第 $0\sim l-1$ 位（正在等待第 $l$ 位）时的最短长度。有两种转移：

• 停止考虑 $i$，转而考虑 $j$。转移为 $f(S\cup\{j\},j,0)\leftarrow f(S,i,l)$，需满足 $j$ 可以接在 $i$ 的第 $l$ 位之后。
• 填一个数。我们可以直接填 $a_{i,l}$，转移为 $f(S,i,l+1)\leftarrow f(S,i,l)+1$。

考虑扩展到一般情况。设 $f(S,i,l,j,r)$ 表示已经考虑了集合 $S$ 中的提示，当前正在考虑的向左走的提示为 $i$，已经填了 $i$ 的第 $l\sim L_i-1$ 位（正在等待第 $l-1$ 位），当前正在考虑的向右走的提示为 $j$，已经填了 $j$ 的第 $0\sim r-1$ 位（正在等待第 $r$ 位）时的最短长度。

注意：我们仍然是从左到右依次填数，所以向左走的提示要从后往前匹配，向右走的提示要从前往后匹配，这导致了两个方向的提示转移方式的不同。

有三种转移：

• 把 $i$ 换成 $k$。转移为 $f(S\cup\{k\},k,x,j,r)\leftarrow f(S,i,0,j,r)$，其中 $x$ 表示所有满足 $i$ 能接在 $k$ 的第 $x$ 位之后的 $x$。
• 把 $j$ 换成 $k$。转移为 $f(S\cup\{k\},i,l,k,0)\leftarrow f(S,i,l,j,r)$，需满足 $k$ 能接在 $j$ 的第 $r$ 位之后。
• 填一个数。枚举填的数 $k$，转移为 $f(S,i,l-[a_{i,l-1}=k],j,r+[a_{j,r}=k])\leftarrow f(S,i,l,j,r)+1$。需满足 $p_{i,k}\le l$（注意不是 $l-1$）且 $p_{j,k}\le r$。

有亿点细节：

我们需要想办法记录当前考虑的提示是否为对应方向的第一个提示。具体地，我们可以新增一个编号为 $n$ 的提示作为占位符（可以认为它的长度为 $0$）。在 $f(S,i,l,j,r)$ 中，若 $i=n$，则表示不再新增向左的提示；若 $j=n$，则表示还没有考虑过向右的提示。

DP 初值为 $f(\varnothing,n,0,n,0)=f(\{i\},i,L_i,n,0)=0$。需要新增一种转移：

• 停止新增向左的提示。转移为 $f(S,n,0,j,r)\leftarrow f(S,i,0,j,r)$。

注意转移顺序。时间复杂度 $\mathcal{O}(2^n (10n)^2\cdot n)$。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,ht[15][15],pos[15][15],st[15],len[15],tr[15][15];
int f[1029][11][11][11][11],cur,ans;
inline int get_tr(int x,int y){
	if((st[x]&st[y])^st[y])return inf;
	int a=pos[y][ht[x][len[x]-1]],b,i;
	if(a==inf)return len[x];
	for(i=len[x]-1;i;--i){
		b=a,a=pos[y][ht[x][i-1]];
		if(a==inf || a>b)break;
	}
	return i;
}
inline void upd(int &x,int y){x>y?x=y:0;}
int main(){
	scanf("%d",&n);
	memset(pos,0x3f,sizeof(pos));
	memset(tr,0x3f,sizeof(tr));
	memset(f,0x3f,sizeof(f));
	for(int i=0,j,x;i<n;++i){
		j=0;
		while(scanf("%d",&x) && x){
			ht[i][j]=--x;
			pos[i][x]=j++;
			st[i]|=1<<x;
		}
		len[i]=j;
	}
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			if(i!=j)tr[i][j]=get_tr(i,j);
	f[0][n][0][n][0]=0;
	for(int i=0;i<n;++i)
		f[1<<i][i][len[i]][n][0]=0;
	ans=inf;
	for(int S=0;S<(1<<n);++S){
		for(int i=0;i<=n;++i){
			for(int l=len[i];~l;--l){
				for(int j=0;j<=n;++j){
					for(int r=0;r<=len[j];++r){
						if((cur=f[S][i][l][j][r])>=inf)continue;
						if(S==(1<<n)-1 && l==0 && r==len[j])upd(ans,cur);
						for(int k=0;k<n;++k){
							if(S>>k&1)continue;
							if(i!=n && l==0)
								for(int x=tr[k][i];x<=len[k];++x)
									upd(f[S|(1<<k)][k][x][j][r],cur);
							if(j==n || r>=tr[j][k])
								upd(f[S|(1<<k)][i][l][k][0],cur);
						}
						if(i!=n && l==0)upd(f[S][n][0][j][r],cur);
						for(int k=0,L,R;k<9;++k){
							if(i==n)L=0;
							else{
								if(pos[i][k]>l)continue;
								L=l-(pos[i][k]==l-1);
							}
							if(j==n)R=0;
							else{
								if(pos[j][k]>r)continue;
								R=r+(pos[j][k]==r);
							}
							upd(f[S][i][L][j][R],cur+1);
						}
					}
				}
			}
		}
	}
	printf("%d\n",ans<inf?ans:-1);
	return 0;
}