题解：P12236 [蓝桥杯 2023 国 Java A] 连续数组

· · 题解

题目传送门

题意分析

通过读题，我们可以知道题目是要求我们构造出一个由数字 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 里一些常见的基本操作吧。

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

具体思路

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

状态

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

边界

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

dp_{2^{i-1},i}=1

转移

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

\\

具体的，枚举 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;
}