一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
using namespace std;
const int N=2, M=(1<<10)+10, H=110, C=150;
using LL=long long;
 
int n, m;
 
class DP
{
public:
    LL f[N][C][H];//第几行，当前状态，多少个, 第二维我们用下标代表状态，减少空间时间
    int cnt[M];//状态的1的数量
    vector<int> correct, pre[C];//左右无相邻1的状态, 当前态能从哪个转移
 
public:
    DP()
    {
        initIO();
    }
 
    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }
 
    //返回x最后一位1
    int lowbit(int x)
    {
        return x&-x;
    }
 
    //得到x二进制含1的数量
    int get1Cnt(int x)
    {
        int sum=0;
        while(x) ++sum, x-= lowbit(x);
        return sum;
    }
 
    //检查x是否有相邻1, 有则true, 否则false
    bool checkL1(int x)
    {
        return x&(x>>1);
    }
 
    //预处理
    void init()
    {
        //fill(cnt[0], cnt[0]+M, 0);✖，元素进行这样的直接指针操作。
        fill(cnt, cnt+M, 0);
//        使用 std::fill(f[0][0][0], f[0][0][0] + x * y * z, 0);
//        报错，可能是因为 C++ 不允许对三维数组的元素进行这样的直接指针操作。
        fill(&f[0][0][0], &f[0][0][0]+N*C*H, 0);
        f[0][0][0]=1;//初始为1
 
        //预处理1数量和无相邻1合法态
        for(int i=0;i<(1<<n);++i)
        {
            cnt[i]=get1Cnt(i);
            if (!checkL1(i)) correct.emplace_back(i);
        }
 
        //cout<<correct.size()<<endl;144最大
        //用下标表示状态
        for(int i=0;i<correct.size();++i)
            for(int j=0;j<correct.size();++j)
            {
                int p=correct[i], q=correct[j];
                if(!checkL1(p|q)&&!(p&q))
                    pre[j].emplace_back(i);
            }
    }
 
    LL work()
    {
        for(int i=1;i<=n;++i)//枚举摆到第几行
        {   //由于状态转移只用到i和i-1行，所以可以二进制优化，但是由于是累加不是求最大值，所以清空i-2行即i行
            fill(&f[i&1][0][0], &f[i&1][0][0]+C*H, 0);
            for(int j=0;j<correct.size();++j)//枚举当前状态
                for(int c=0;c<=m;++c)//枚举已经放了几个
                    if(c>=cnt[correct[j]])//摆了几个>=当前行的数量
                        for(auto &p:pre[j])//枚举当前可从哪个状态转移过来
                            f[i&1][j][c]+=f[i-1&1][p][c-cnt[correct[j]]];
        }
            
        LL ans=0;
        for(int i=0;i<correct.size();++i)
            ans+=f[n&1][i][m];
        return ans;
    }
}dp;
 
int main()
{
    cin>>n>>m;
    dp.init();
    cout<<dp.work();
}