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

· · 题解

此题注意到数据范围 1 \le N \le 15，且最后的问题是有多少种满足条件的连续数组，于是容易想到状压 DP。

解题过程

首先我们想该如何设计状态呢？首先第一维 i 想表示的是用到了哪些数，所以用 i 的二进制来表示这些状态。那么会不会有第二维呢？因为题目中还规定了两个相邻的数组元素的关系，所以还要有第二维 j 表示的是以 j 为结尾。于是就确定了状态：dp_{i,j} 表示在 i 的二进制下用到了一些数，并以 j 为结尾，这样子有多少种满足条件的连续数组。

确定状态是较难的一步，接下来就还好了。如何初始化？显然初始化只用一个数的情况，十分容易。

接下来就到了状态转移，我们先枚举 i 和 j，注意 j 在先前是要用到的，再枚举一个数 k 为 j 后面相邻的数（需要注意 k 在先前没有用到），当 k 满足相邻元素的关系时，就可以进行状态转移，令加入 k 后的状态压缩成二进制后变成了 x，就可以进行状态转移：

dp_{x,k} = dp_{x,k} + dp_{i,j}

最后答案就是把所有数字结尾的情况相加即可。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 15;
int n;
ll dp[1 << N][N + 5];
bool pd[N + 5];
int js(int x){//计算x的二进制下有多少个1 
    int ct = 0;
    while(x){
        if(x & 1) ct++;
        x >>= 1;
    }
    return ct;
}
int main(){
    cin >> n;
    for(int i = 1;i < n;i++) cin >> pd[i];
    //初始化 
    for(int i = 0;i < n;i++) dp[1 << i][i] = 1;
    int z = 1 << n;
    for(int i = 1;i < z;i++){//第一层循环i 
        for(int j = 0;j < n;j++){//第二层循环j 
            if(!(i & (1 << j))) continue;//j一定是用到的，不满足条件就到不了下一层循环 
            int wz = js(i);//这是为了算一共用了几个数 
            for(int k = 0;k < n;k++){//枚举k 
                //条件1：k在先前没有出现
                //条件2：满足这两个元素之间的关系 
                if(!(i & (1 << k)) && (pd[wz] == 1 && k == j + 1 || pd[wz] == 0 && k != j + 1)){
                    dp[i | (1 << k)][k] += dp[i][j];//状态转移 
                }
            }
        }
    }
    ll ans = 0;
    //统计答案 
    for(int i = 0;i < n;i++) ans += dp[z - 1][i];
    cout << ans;
    return 0;
}