题目描述

状态压缩dp
1. 枚举合法状态
2. 枚举合法状态的可转移到的状态head[a][i]
3. 开始dp，对于每一个合法状态，计算它的可转移状态之和

#include <iostream>
#include <vector>
using namespace std;

int n,m;
//第i行内部不能有两个1相邻
//第i行和i-1行不能相互攻击到
//a&b一定要=0
//a|b一定不能有两个相邻的1

typedef long long ll;
const int N=12,M=1<<10,K=110;

vector<int> state;
//head存可转移到的状态
vector<int> head[M];

ll f[N][K][M];
//每个状态有多少个1
int cnt[M];

int check(int x)
{
    for(int i=0;i<n;i++)
    {
        if((x>>i &1) &&(x>>i+1 &1))
        return 0;
    }
    return 1;
}

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

int main()
{
    cin>>n>>m;
    for(int i=0;i<1<<n;i++)
    {
        if(check(i))
        {
            state.push_back(i);
            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];
            //记录a可以转移到的状态b
            if((a&b)==0 &&check(a|b))
            {
                head[i].push_back(j);
            }
        }
    }
    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int a=0;a<state.size();a++)
            {
                for(int b=0;b<head[a].size();b++)
                {
                    int t=head[a][b];
                    int c=cnt[state[a]];
                    if(j>=c)
                    {
                        f[i][j][a]+=f[i-1][j-c][t];
                    }
                }
            }
        }
    }
    cout<<f[n+1][m][0];

    return 0;
}

二刷，注意几个坑

1. 枚举状态时是for(int i=0;i<1<<n;i++)

三刷，又有坑

1. 在做dp时j要从0开始，不能从1开始
2. 初始化为f[0][0][0]=1;

//先把合法状态表示出来，再计算状态转移
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N=1<<12;
long long f[12][110][N];
int cnt[N];
int n,m;
vector<int> state;
vector<int> head[N];

int check(int a)
{
    for(int i=0;i<=n;i++)
    {
        if(a>>i & a>>(i+1) & 1)
        {
            return 0;
        }
    }
    return 1;
}

int count(int a)
{
    int cnt=0;
    while(a)
    {
        if(a&1) cnt++;
        a=a>>1;
    }
    return cnt;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<1<<n;i++)
    {
        if(check(i)) state.push_back(i);
        cnt[i]=count(i);
    }

    for(int i=0;i<state.size();i++)
    {
        for(int j=0;j<state.size();j++)
        {
            int a=state[i];
            int b=state[j];
            if(check(a|b) && (a&b)==0)
            {
                head[i].push_back(j);
            }
        }
    }

    f[0][0][0]=1;


    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<=m;j++)
        {
            //第i行是状态a，摆放了j个国王
            for(int k=0;k<state.size();k++)
            {
                for(int t : head[k])
                {
                    int a=state[k];

                    if(j>=cnt[a])
                        f[i][j][k]+=f[i-1][j-cnt[a]][t];
                }
            }
        }
    }
    cout<<f[n+1][m][0];

    return 0;
}