题目:
题目描述
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。
注:数据有加强(2018/4/25)
输入格式
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
输出格式
所得的方案数
输入输出样例
输入 #1
3 2
输出 #1
16
题解:
dp[i][j][k]:第i行状态为j,且截至到第i行已经放置了k个国王的方案数
这个状态dp因为(i,j)位置有国王,附近八个位置都不可以放国王,所以状态互斥多了一点
dp转移方程:
dp[i][j][r]+=dp[i-1][k][r-num_1[j]];
num_1[j]表示第i个状态中包含国王的数量
最后把所有dp[n][1--num][k]加起来输出就可以
1--num是指所有状态
代码:
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> using namespace std; #define mem(a) memset(a,0,sizeof(a)) #define mem__(a) memset(a,-1,sizeof(a)) typedef long long ll; const int maxn=10; const int N=200; const int INF=0x3f3f3f3f; const double blo=(1.0+sqrt(5.0))/2.0; const double eps=1e-8; ll state[N],dp[maxn][N][105],num_1[N]; int main() { ll n,m,num=0,sum=0; scanf("%lld%lld",&n,&m); for(ll i=0; i<(1<<n); ++i) { if((i&(i<<1)) || (i&(i>>1))) continue; state[num]=i; ll k=i; //printf("%lld ",i); while(k) { if(k&1) num_1[num]++; k>>=1; } //if(num_1[num]<=m) num++; //else num_1[num]=0; } //printf(" "); //printf("%lld*** ",num); for(ll i=0; i<num; ++i) { dp[0][i][num_1[i]]=1; //if(num_1[i]==k) sum++; } ll maxx=0; for(ll i=1; i<n; ++i) { for(ll j=0; j<num; ++j) { for(ll k=0; k<num; ++k) { if((state[j]&state[k]) || ((state[j]<<1)&state[k]) || (state[j]&(state[k]<<1))) continue; for(ll r=m;r>=num_1[j];--r) { dp[i][j][r]+=dp[i-1][k][r-num_1[j]]; } } } } for(ll i=0;i<num;++i) { maxx+=dp[n-1][i][m]; } printf("%lld ",maxx); return 0; }