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

思路简述

题意很好理解，不再过多赘述。

看到

n

的取值范围那么小，第一时间想到记忆化搜索，但仔细审完题发现状压 DP 更简单。

理论上来看题解的应该都知道什么是状压 DP，但还是简单介绍一下。

所谓状压 DP，其精髓在于状态压缩，通过将状态转化为二进制的方式进行动态规划，利用二进制中只有

1

和

0

的特性表示某点是否达到某个目的。

定义

dp_{i,j}

为当使用的状态为

i

，最后用的一个数为

j

时共有几种方案。其中状态

i

中

1

为用过，

0

为没用过。

接下来很简单了，遍历所有状态，记录下每种状态中用了几个数，用变量

pos

记下来。再枚举数字

j

和

k

，表示当前状态下最后一个用的数为

j

，下一个要用的数为

k

。转移也很简单，无非是 dp[i|(1<<k-1)][k]+=dp[i][j];。转移之前记得判一下

a_{pos}

是

1

还是

0

。根据题目条件，如果是

0

只有

k=j+1

时才可以转移，否则只有

k\ne j+1

时才可转移。我的代码里使用三目运算符来判断的，如果太丑的话注释里的内容是等价的。

代码呈现

C++

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=16;
int n,a[N],dp[1<<N][N],ans;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++) cin>>a[i],dp[1<<i-1][i]=1;//输入的同时初始化 
	dp[1<<n-1][n]=1; 
	int num=1<<n;
	for(int i=0;i<num;i++){
		int pos=0,temp=i;
		while(temp){
			pos+=(temp&1);//计算已用过的数字的数量 
			temp=temp>>1;
		}
		for(int j=1;j<=n;j++){
			if(!(i>>j-1)&1) continue;//确保j在i中 
			for(int k=1;k<=n;k++){
				if((i>>k-1)&1) continue;//确保k不在i中 
				if(a[pos]) dp[i|(1<<k-1)][k]+=(k==(j+1)?dp[i][j]:0);//转移方程，注释中的代码作用相同 
				else dp[i|(1<<k-1)][k]+=(k!=(j+1)?dp[i][j]:0);
				/*
				if(a[pos]){
					if(k==j+1) dp[i|(1<<k-1)][k]+=dp[i][j];
				}
				else{
					if(k!=j+1) dp[i|(1<<k-1)][k]+=dp[i][j];
				}
				*/
			}
		}
	}
	for(int i=1;i<=n;i++) ans+=dp[num-1][i];//累加不同数字作为末尾时的方案数 
	cout<<ans;
	return 0;
}

Java

JAVA

import java.util.Scanner;
public class Main {
    static final int N=16;
    static int n,a[]=new int[N];
    static long dp[][]=new long[1<<N][N],ans;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<n;i++){a[i]=sc.nextInt();dp[1<<i-1][i]=1;}
        dp[1<<n-1][n]=1;
        int num=1<<n;
        for(int i=0;i<num;i++){
            int pos=0,temp=i;
            while(temp!=0){pos+=(temp&1);temp>>=1;}
            for(int j=1;j<=n;j++){
                if(((i>>j-1)&1)==0)continue;
                for(int k=1;k<=n;k++){
                    if(((i>>k-1)&1)!=0)continue;
                    if(a[pos]!=0)dp[i|(1<<k-1)][k]+=(k==j+1?dp[i][j]:0);
                    else dp[i|(1<<k-1)][k]+=(k!=j+1?dp[i][j]:0);
                }
            }
        }
        for(int i=1;i<=n;i++)ans+=dp[num-1][i];
        System.out.println(ans);
    }
}

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

文章操作

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

思路简述

代码呈现

C++

Java

The end.

相关推荐

评论

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