蓝桥集训之小国王

蓝桥集训之小国王

• 核心思想：状态压缩dp

  • 将每张图对应的上一张符合要求的图存入二维数组
  • 依次取出并更新当前值

•   #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    typedef long long LL;
    const int N = 15,M = 1<<10,K = 110;
    
    LL f[N][K][M];
    int n,m;
    int cnt[M];
    vector<int> states;
    vector<int> h[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)  //求有多少1
    {
        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))
            {
                states.push_back(i);
                cnt[i] = count(i);
            }
            
        for(int i=0;i<states.size();i++)  //求前一行符合
            for(int j=0;j<states.size();j++)
            {
                int a = states[i] , b = states[j];
                if((a&b) == 0 && check(a|b))
                    h[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<states.size();a++)
                    for(auto b : h[a])  //a和j都从头遍历了一遍
                    {
                        int c = cnt[states[a]];
                        if(j>=c) f[i][j][a] += f[i-1][j-c][b];
                    }
        cout<<f[n+1][m][0];
    }