1592 例题1 国王(Sgu223 LOJ10170 LUOGU1896 提高+/省选-) 暴力思考 状压DP 01背包

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

在线测评地址(LUOGU)

1.暴力算法探讨

样例

输入
3 2
输出
16

解释如下

 a与A在统计方案数时不做区分。

考虑了暴力的算法时间复杂度，在极端条件下:n=10 时，有100个格子，假定有100个棋子，

100*99*98*97*......*3*2*1=9.33*10^157天文数字。

暴力耗时，编编也麻烦。

该题的难度早已超越了八皇后，并且，限制越多，暴力编写越麻烦。

2.状压DP

ybt

通过

LOJ

LUOGU

首先，看到这题，就知道如果不是搜索，就是DP。当然搜索是过不了的，所以就应该尝试想出DP的解法。

DP的前提之一当然是要找出一个可以互相递推的状态。显然，目前已使用的国王个数当然必须是状态中的一个部分，因为这是一个限制条件。那么除此之外另外的部分是什么呢？

我们考虑到每行每列之间都有互相的约束关系。因此，我们可以用行和列作为另一个状态的部分（矩阵状压DP常用行作为状态，以下的论述中也用行作为状态）。

又看到数据范围： 1 <=N <=10。这里我们就可以用一个新的方法表示行和列的状态：数字。考虑任何一个十进制数都可以转化成一个二进制数，而一行的状态就可以表示成这样——例如：

1010(2)   (2)表示二进制

表示：这行的第一个格子没有国王，第二个格子放了国王，第三个格子没有放国王，第四个格子放了国王（注意，格子从左到右的顺序是与二进制从左到右的顺序相反的，因为真正在程序进行处理的时候就像是这样的）。而这个二进制的数就可以转化成十进制：

10(10)  (10)表示十进制

于是，我们的三个状态就有了：第几行（用i表示）、此行放什么状态（用j表示）、包括这行已经使用了的国王数（用s表示）。

考虑状态转移方程。我们预先处理出每个状态（sit[x]表示放置国王的状态,如二进制1010(2)，对应十进制10(10) ) (sit是situation的缩写),(x表示第x个有效数据)，及此状态下这行放的国王个数（gs[x]）(x表示第x个有效数据) (gs是中文 国王数量 拼音的缩写)，(如n=3，行上有效的状态数量是5个，如下:)

预处理代码如下

int tot=0,sit[2000],gs[2000];//tot用来统计有效行的数量.每行最多10列,每行状态总数量最多2^10=1024,故2000够用 
//st表示该行状态,sum表示使用国王的数量,pos表示下一次需要操作的格子位置
//dfs 用来处理出有效行的数据 
void dfs(int st,int sum,int pos){//st,sum是当前位置的数据,pos是下一个位置 
	if(pos>=n){//每行,下一次处理位置,达到格子边界,或者越过格子边界.n表示棋盘每行对应的格子数  
		tot++;
		sit[tot]=st;//tot表示当前总的有效行数
		gs[tot]=sum;
		return;//新建一个状态
	}
	//第pos个格子不放国王，那么第pos+1格子可放或不放国王
	dfs(st,sum,pos+1);//当前行中处理的格子位置不放置国王
	//第pos个格子放国王,那么第pos+1个格子不放国王,第pos+2个格子可放或不放国王  
	dfs(st+(1<<pos),sum+1,pos+2);//当前行中处理的格子位置放置国王 
}

预处理调用代码如下

dfs(0,0,0);

于是就有：

dp[i][sit[k]][s]=sum(dp[i−1][sit[j]][s−gs[k]])，dp[i][sit[k]][s]就表示在只考虑前i行时，在前i行（包括第i行）有且仅有s个国王，且第i行国王的情况是编号为k的有效行状态时情况的总数。而j就代表第i-1行的国王情况的有效行状态编号

其中j,k在1到tot之间，j与k都表示状态的编号，且k与j必须满足两行之间国王要满足的关系。（对于这一点的处理我们待会儿再说）

这个状态转移方程也十分好理解。其实就是上一行所有能够与这一行要使用的状态切合的状态都计入状态统计的加和当中。其中i、j、k、s都要枚举。

再考虑国王之间的关系该如何处理呢？在同一行国王之间的关系我们可以直接在预处理状态时舍去那些不符合题意的状态，而相邻行之间的关系我们就可以用到一个高端的东西：位运算。由于状态已经用数字表示了，因此我们可以用与（&）运算来判断两个状态在同一个或者相邻位置是否都有国王——如果：

sit[j]&sit[k](即上下有重复的king) ,如下：

(sit[j]<<1)&sit[k](即左上右下有重复king),如下：

sit[j]&(sit[k]<<1)(即右上左下有重复king)

这样就可以处理掉那些不符合题意的状态了。

总结一下。其实状压DP不过就是将一个状态转化成一个数，然后用位运算进行状态的处理。理解了这一点，其实就跟普通的DP没有什么两样了。

最后上代码（注意其中的一些细节处理）：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL dp[15][2000][110];//dp[自第1行开始的运行到的行号][有效的行状态][该行使用的国王数量],
int n,num;
int tot=0,sit[2000],gs[2000];//tot用来统计有效行的数量.每行最多10列,每行状态总数量最多2^10=1024,故2000够用 
//st表示该行状态,sum表示使用国王的数量,pos表示下一次需要操作的格子位置
//dfs 用来处理出有效行的数据 
void dfs(int st,int sum,int pos){//st,sum是当前位置的数据,pos是下一个位置 
	if(pos>=n){//每行,下一次处理位置,达到格子边界,或者越过格子边界.n表示棋盘每行对应的格子数  
		tot++;
		sit[tot]=st;//tot表示当前总的有效行数
		gs[tot]=sum;
		return;//新建一个状态
	}
	//第pos个格子不放国王，那么第pos+1格子可放或不放国王
	dfs(st,sum,pos+1);//当前行中处理的格子位置不放置国王
	//第pos个格子放国王,那么第pos+1个格子不放国王,第pos+2个格子可放或不放国王  
	dfs(st+(1<<pos),sum+1,pos+2);//当前行中处理的格子位置放置国王 
}
int main(){
	int i,j,k,s;
	LL ans=0;
	scanf("%d%d",&n,&num);
	dfs(0,0,0);
	for(i=1;i<=tot;i++)//初始化,很重要,别忘了 
		dp[1][sit[i]][gs[i]]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=tot;j++)//j是属于第i-1行的有效行的位次 
			for(k=1;k<=tot;k++){//k是属于第i行的有效行的位次 
				if(sit[j]&sit[k])continue;
				if((sit[j]<<1)&sit[k])continue;
				if(sit[j]&(sit[k]<<1))continue;//不合法的跳过 
				for(s=num;s>=gs[k];s--)
					dp[i][sit[k]][s]+=dp[i-1][sit[j]][s-gs[k]];
			}
	for(j=1;j<=tot;j++)
		ans+=dp[n][sit[j]][num];
	printf("%lld\n",ans);
	return 0;
}