洛谷 P1896 [SCOI2005]互不侵犯 (状压dp)

Oriole ·

更新时间:2024-09-21

· 947 次阅读

洛谷 P1896 [SCOI2005]互不侵犯

洛谷链接

题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入格式

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式

所得的方案数

输入输出样例

输入 #1
3 2
输出 #1
16

Solution

棋盘类状态压缩dp

因为要放置k个棋子，所以加一维，令dp[i][j][k] 为i行合法的第j个状态放置k枚棋子的方案数，按先处理同行去除非法方案数，再处理相邻行状态转移即可

详细过程见代码及注释

代码

#include
using namespace std;
typedef long long ll;
const int SZ = 100 + 5;
const int INF = 0x3f3f3f3f;
int N,n,m,tot,sta[SZ],onenum[SZ];;
ll dp[11][SZ][SZ];//dp[i][j][k] i行 j状态 摆放k个 
ll ans;
inline int getone(int x) //求1的数量
{
	int sum = 0;
	while(x)
	{
		sum ++ ;
		x &= x - 1;
	}
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	N = 1 << n;
	for(int i = 0 ;i < N;i ++ )//2^n - 1
	{
		if(i & i << 1)  continue; //同一行左右相邻 
		sta[ ++ tot] = i; //可行状态 
		onenum[tot] = getone(i);//该状态1的数量 
		dp[1][tot][onenum[tot]] = 1; //边界 第一行 
	} 
	for(int i = 2;i <= n;i ++ ) //当前行 
		for(int j = 1;j <= tot;j ++ ) //当前行的状态      
			for(int k = 1;k <= tot;k ++ )  //上一行的状态    先枚举当前行还是上一行根据实际情况 
			{
				//排除非法状态 
				if(sta[j] & sta[k]) continue; 	//正下 
				if(sta[j] & sta[k] << 1) continue; //右下 
				if(sta[j] << 1 & sta[k]) continue; //左下 
				for(int l = onenum[j];l <= m;l ++ )
					dp[i][j][l] += dp[i - 1][k][l - onenum[j]];  
			} 
	for(int i = 1;i <= tot;i ++ )
		ans += dp[n][i][m]; //ans = Σdp[n][i][m] 
	printf("%lld",ans); 
	return 0;
}

2020.4.8

作者：October's very own

dp p1

1024 个赞