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

· · 题解

题解：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++

#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

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

The end.