自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:54:39，当前版本为作者最后更新于2024-09-12 21:28:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

数据范围表明这是状压 dp。

但是发现如果真的压缩状态需要使用第 $i$ 位用 $i$ 进制存储的方式来存储状态，太麻烦，所以干脆不压了。

设 $dp_{p,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8}$ 表示填到第 $p$ 位，且上一个数 $x$ 到第 $p$ 位的距离为 $a_x$ 时，填完剩下位置的方案个数。

因为当 $a_x\ge x$ 时我们不需要关系它具体在哪个位置，只需要知道 $a_x$ 是大于等于 $x-1$ 的就行，所以把 $a_x\ge x$ 的状态全部压缩成 $x-1$。

这里用记忆化搜索实现，每次只需要枚举第 $p$ 位填的数即可，合法状态就继续 dfs，$p=n+1$ 就返回 $1$。

#include<bits/stdc++.h>
using namespace std;
int dp[105][1][2][3][4][5][6][7][8];//dp[i][a1][a2][a3][a4][a5][a6][a7][a8]：第 p 位，且上一个 x 到第 p 位的距离为 ax 时，填的方案个数
int mod=1e9+7;
int n;
bool b[10];
int dfs(int p,int a1,int a2,int a3,int a4,int a5,int a6,int a7,int a8){
	//cout<<p<<" "<<a1<<" "<<a2<<" "<<a3<<" "<<a4<<" "<<a5<<" "<<a6<<" "<<a7<<" "<<a8<<endl;
	if(dp[p][a1][a2][a3][a4][a5][a6][a7][a8]!=-1)return dp[p][a1][a2][a3][a4][a5][a6][a7][a8];
	if(p==n+1)return 1;
	//枚举这一位填的数
	int ans=0;
	int a[10]={0,a1+1,a2+1,a3+1,a4+1,a5+1,a6+1,a7+1,a8+1};//到 i+1 的距离
	for(int i=1;i<=8;i++)if(b[i]){
		if(a[i]==i){//可以填 i
			int tmp=a[i];
			a[i]=0;//方便下一行
			ans+=dfs(p+1,min(a[1],0),min(a[2],1),min(a[3],2),min(a[4],3),min(a[5],4),min(a[6],5),min(a[7],6),min(a[8],7));
			ans%=mod;
			a[i]=tmp;//还原
		}
	}
	return dp[p][a1][a2][a3][a4][a5][a6][a7][a8]=ans;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	memset(dp,-1,sizeof(dp));
	int m;cin>>n>>m;
	while(m--){
		int x;cin>>x;b[x]=1;
	}
	cout<<dfs(1,0,1,2,3,4,5,6,7);
	return 0;
}