题目描述
在 n×n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n 和 k。
输出格式
共一行,表示方案总数,若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n2
样例
输入样例:
3 2
输出样例:
16
与八皇后问题有点类似,但是这个dfs肯定是不行的,那么就考虑状态压缩dp,直接写的话也会超时,还需要有一点点的优化,,就是考虑的时候要考虑自己行有没有冲突,以及考虑与上一行有没有冲突,与上一行有没有冲突只能每次枚举判断,进行转移,但是与自己行有没有冲突,我们可以通过预处理,把所有自己与自己不冲突的状态找出来,在每次只考虑这些状态的情况下进行枚举,能优化很多时间。
还有一个问题是最后求的是刚好放k个国王时候的方案数,就要再加一维,dp[i][j][r]表示,前i行已经放好,第i行状态为j,当前放置的国王数为r的情况下的方案数。转移的时候,要在保证不超过k个国王的前提下进行转移,其实每次都有个求当前状态有几个1的过程,我们同样可以把这一步预处理出来~。
时间复杂度: 优化前是2^n * 2^n * n * k的,优化后,我看了看,基本每个n对应的满足条件的状态数是n^2左右,那么时间复杂度降了非常多,大概n^5 * k …这个复杂度自己瞎算的,大佬勿喷
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 1<<11;
ll dp[11][N][105],top=0;
int tem[N],num[N];
int get(int x)
{
int ans=0;
while(x)
{
if(x&1) ans++;
x>>=1;
}
return ans;
}
int main()
{
int n,m; //把k换成了m,下同
cin>>n>>m;
dp[0][0][0]=1;
ll ans=0;
for(int i=0;i<(1<<n);i++) //预处理
{
if(i&(i<<1) ) continue;
tem[top]=i;num[top++]=get(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<top;j++)
for(int k=0;k<top;k++)
{
//判断与上一行是否冲突
if(tem[j]&tem[k] || (tem[j]<<1)&tem[k] || (tem[j]>>1&tem[k])) continue;
for(int r=0;r<=m;r++)
if(r+num[k]<=m) //必须放置不超过m个国王
dp[i][k][r+num[k]]+=dp[i-1][j][r];
}
}
for(int i=0;i<top;i++) ans+=dp[n][i][m];
cout<<ans<<endl;
return 0;
}
大佬,请问为什么初始化是f[0][0][0] = 1, 而不是f[i][0][0] = 1 (0 <= i <= n),我对初始化这个不是很理解吗,请麻烦告知一下呗。
因为所有的状态都是从上一行的某个状态转移过来,如果所有行一个国王也不放,只有一种方案,如果像你那样初始化,每一行的0的状态是不会与上一行冲突的,那么就会加上上一行的方案数,计算完之后的dp[n][0][0]的方案数是n。会多算。你可以自己输出一下试试。
明白了谢谢大佬