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

Solution

这道题目有点难看出该如何设计状态。但是我们注意到题目中所说的

nums

中的元素取值范围为

1∼N

，就发现我们的状态

i

其实表示一个数字是否用过，然后还要另有一个状态

j

表示最后一个用到的数字，那么这道题目就很简单了。另外枚举一个数字

k

，可得出状态转移方程，读者自证不难。

dp_{i,j}=dp_{i,j}+dp_{i-2^j,k}

但这个方程并不是随便乱用的，还得符合题目要求。还得判断

j

和

k

是有序还是无序，具体的可以看代码。

至于初始化，当然是以每个数字开头的情况赋值为

1

，其他的为

0

。答案的话，就是

\sum_{i=0}^{n-1}{dp_{2^n-1,i}}

将以不同数字结尾的每种情况统计起来即可。

AC code

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[16],dp[1<<16][16];
int num(int x){//这个num是用于计算一个数字在二进制下有多少个 1
	int res=0;
	while(x){
		x-=x&(-x);
		res++;
	}
	return res;
}
signed main(){
	cin>>n;
	for(int i = 1;i<n;i++) cin>>a[i];
	for(int i = 0;i<n;i++) dp[1<<i][i]=1;
	for(int i = 1;i<1<<n;i++){
		for(int j = 0;j<n;j++){
			if(i&(1<<j)==0) continue;
			for(int k = 0;k<n;k++){
				if(j==k||i&(1<<k)==0) continue;
				if(a[num(i)-1]==0&&j==k+1) continue;
				if(a[num(i)-1]&&j!=k+1) continue;
				dp[i][j]+=dp[i^(1<<j)][k];
			}
		}
	}
	int ans=0;
	for(int i = 0;i<n;i++) ans+=dp[(1<<n)-1][i];
	cout<<ans;
	return 0;
}

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

文章操作

Solution

AC code

相关推荐

评论

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