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

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