hoj2662 状态压缩dp

时间：2022-04-05 22:45:12

Pieces Assignment

My Tags   (Edit)
  Source : zhouguyue
  Time limit : 1 sec   Memory limit : 64 M

Submitted : 444, Accepted : 156

Background

有一个n*m的棋盘(n、m≤80,n*m≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻（每个棋子最多和周围4个棋子相邻）。求合法的方案总数。

Input

本题有多组测试数据，每组输入包含三个正整数n,m和k。

Output

对于每组输入，输出只有一个正整数，即合法的方案数。

Sample Input

2 2 3

4 4 1

Sample Output

0
16
 
由于棋子位置不同，相同妻子个数的棋盘又有多种状态，所以考虑用状态压缩dp。
dp[i][j][k]表示第i行，有j个棋子，状态为k的个数。
dp[i][j][k] = sum{ dp[i-1][j-num[k][t] };（保证合法的状态下）。
 
 
#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define INF 1000000007

#define mod 100000000

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN = ;

int n,m,K,cnt;

ll dp[][][];

ll q[<<MAXN];

int num[];

int getnum(int x)

{

    int cnt = ;

    while(x){

        if(x & )cnt ++;

        x >>= ;

    }

    return cnt;

}

void Init()

{

    cnt = ;

    memset(num,,sizeof(num));

    //得到所有满足条件的合法的状态

    for(int i = ; i < ( << m); i++){

        if(!(i & (i << ))){

            num[cnt] = getnum(i);

            q[cnt++] = i;

        }

    }

}

int main()

{

    while(~scanf("%d%d%d",&n,&m,&K)){

        if(n < m){

            swap(n,m);

        }

        Init();

        memset(dp,,sizeof(dp));

        for(int i = ; i < cnt; i++){

            if(num[i] > K)continue;

            dp[][num[i]][i] = ;//第一行能够放num[i]个棋的状态为i的个数有1个

        }

        for(int i = ; i <= n; i++){//枚举行数

            for(int j = ; j <= K; j++){//枚举棋子个数

                for(int k = ; k < cnt; k++){//枚举状态

                    if(num[k] > j)continue;//如果当前状态的num[k]个数大于j个 不合法

                    for(int t = ; t < cnt; t++){

                        if((q[t]&q[k]) || num[t] > j)continue;//有相交或者个数不合法

                        dp[i][j][k] += dp[i-][j-num[k]][t];//第i行个数为j个棋子的状态为k的个数 等于所有

                                                            //上一行用了j-num[k]个棋子的状态为t的和。

                    }

                }

            }

        }

        ll ans = ;

        for(int i = ; i < cnt; i++){

            ans += dp[n][K][i];

        }

        cout<<ans<<endl;

    }

    return ;

}

相关文章