题目描述

注释版，仅记录。

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;

typedef long long LL;

const int N=12,M=1<<10,K=110;
LL f[N][K][M];
int n,m;
vector<int> state;  //每一个状态
int id[M],cnt[M];
vector<int> head[M];    //每一个状态可转移的其他状态


bool check(int state)   //检查每个状态中是否存在连续的两个1
{
    for(int i=0;i<n;i++)
        if((state>>i &1) && (state >> i + 1 & 1))
        return false;
    return true;
}

int count(int state)
{
    int res=0;
    for(int i=0;i<n;i++) res+=state>>i&1;
    return res;
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<1<<n;i++)
    {
        if(check(i))
        {
            state.push_back(i);     //先预处理掉不可能符合的状态（1相邻）
            cnt[i]=count(i);
        }
    }

    for(int i=0;i<=state.size();i++)
    {
        for(int j=0;j<state.size();j++)
        {
            int a=state[i],b=state[j];
            if((a&b)==0 && check(a|b))  //预处理a是否能够转移到b
                head[i].push_back(j);
        }
    }

    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++)     //枚举到第n+1行，便于输出
    {
        for(int j=0;j<=m;j++)
        {
            for(int a=0;a<state.size();a++)
            {
                for(int b:head[a])  //b是上一行的状态，必须能由a转移过来
                {
                    int c=cnt[state[a]];
                    if(j>=c)
                    {
                        f[i][j][a]+=f[i-1][j-c][b];
                    }
                }
            }
        }
    }

    cout<<f[n+1][m][0]<<endl;

    return 0;
}