此题注意到数据范围

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}

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

代码

CPP

#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;
}

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

文章操作

解题过程

代码

相关推荐

评论

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