自动搬运

查看原文

来自洛谷，原作者为

	guoshengyu1231 **

搬运于2025-08-24 23:13:54，当前版本为作者最后更新于2025-04-20 15:22:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

题意分析

通过读题，我们可以知道题目是要求我们构造出一个由数字 $1$ 到 $n$ 组成的序列，使得数列中每两个相邻的数满足以下两个条件之一：$\\$

1. 满足 $a_{i+1}=a_i+1$。
2. 满足 $a_{i+1}\ne a_i+1$。

当接下来输入的 $s_i$ 等于 $1$ 时，则需要 $a_{i+1}$ 满足条件 $1$，否则满足条件 $2$。

$\\$ 考虑到对于所有评测用例，满足 $1\le n\le 15$，那应该要么是记忆化搜索，要么是状态压缩 dp（其实都是 dp 的思想，只是求解方向不同）。

状态压缩简介

假设现在有一个集合，集合内有 $n$ 个元素，分别对应 $n$ 个物品。对于每个物品，我们可以是选或不选，用数字 $0$ 和 $1$ 表示。这样我们就可以得到一个由数字 $0$ 和 $1$ 组成的集合。这个集合里的元素要么是 $0$，要么是 $1$。$\\$ 要么是 $0$，要么是 $1$……这不就是二进制吗！所以我们就可以用一个二进制数来存储这些状态。用一个数来存储一些状态，这就是状态压缩的根本原理。 $\\$

既然提到了状态压缩 dp，那我就顺便讲一下状态压缩 dp 里一些常见的基本操作吧。

• 查询集合 $S$ 的第 $i$ 位是否为 $1$（从 $0$ 开始）：(S>>i)&1或S&(1<<i)。
• 将集合 $S$ 的第 $i$ 位置 $0$（从 $0$ 开始）：S^(1<<i)或(S>>i)^1。
• 将集合 $S$ 的第 $i$ 位置 $1$（从 $0$ 开始）：S|(1<<i)或(S>>i)|1。

其实有关状态压缩的二进制操作就这么些，关键是如何运用这些操作来解决问题。这些操作只是来帮助你解决问题的，所以关键还是具体思路。

具体思路

虽然是叫状态压缩 dp，但是他的本质依然是 dp。万变不离其宗，既然是 dp，那三要素可不能少。

状态

首先不难想到用一个二进制状态来表示选了哪些数字，但接下来我们还需要什么呢？当你实在想不到还需要什么时，你可能会认为应该没有了。但当你再一次读题时，你发现你还忽略了一个限制条件，那就是相邻两个数的限制。那这该怎么办呢？既然是相邻两个数，那必然有前一个数和后一个数，所以我们还得再设一个状态 $last$ 表示最后一个数是多少。这下应该是可以了。

边界

不难想到，当只有一个数的时候，此时肯定只要一种方案，所以可以很容易确定边界：

转移

接下来来到最难的一步：转移。我们知道，这题只限制相邻两个数，那我们已经知道了前一个数，只需要枚举后一个数就行了。 $\\$

具体的，枚举 $next$ 为下一个数，当然，这个数肯定不是出现在原集合中的，如果 $last$ 和 $next$ 满足条件，那么就定义新集合 $newS=S+next$，让 $dp_{newS,next}$ 加上 $dp_{S,last}$ 就行啦！

参考代码

#include<bits/stdc++.h>
#define int long long//不开long long见祖宗
using namespace std;
int n,a[20];
int dp[1<<20][20];
int pop_count(int x)
{
    int cnt=0;
    while(x)
     {
        if(x&1) cnt++;
        x>>=1;
     }
    return cnt;
}//统计二进制数中1的数量
signed main()
{
    cin>>n;
    for(int i=1;i<n;i++) cin>>a[i]; //输入
    for(int i=1;i<=n;i++) dp[1<<i-1][i]=1;//边界（初始化）
    for(int s=1;s<(1<<n)-1;s++)
     for(int i=1;i<=n;i++)//同题解中的last
      if((s>>i-1)&1)//如果i属于s 
       {
           int k=pop_count(s);//计算i是第几位
           for(int j=1;j<=n;j++)//同题解中的next
            if(!((s>>j-1)&1))//如果j不属于s
             {
                if(a[k]^(i+1==j)) continue;//如果不满足条件限制，则重开
                int new_s=s|(1<<j-1);
                dp[new_s][j]+=dp[s][i];//状态转移
             }
       }
    int ans=0;
    for(int i=1;i<=n;i++) ans+=dp[(1<<n)-1][i];//计算答案
    cout<<ans;
    return 0;
}