|
题面 在 n * n ( n <= 20 ) 的方格棋盘上放置 注意：同一行或同一列只能有一个车，否则会相互攻击 输入格式输入文件第一行，有两个数 下面有 输出格式输出文件也只有一行，即得出的方案总数。 样例样例输入样例输出1
分析 一如既往的，状态压缩动态规划。 限制分为两部分：棋盘本身的限制 ， ”车（ju）“自身的限制。
我们使用a数组记录棋盘本身的限制即可，a [ x ]表示第x行限制情况所对应的十进制数字。
这道题的有一个有意思的地方：一行里只能有一个车，一列里只能有一个车。 一行里只能有一个车，意思就是，我们可以只用一个二进制串s，就可以表示之前所有行（包括目前行）一共放置的车的状态了！ 同时，这个限制串中"1"的个数，就是我们目前所在的行号！ 特别注意，这个s串中，包括目前行的那个“1”！
比如我们有限制串：01101 那么我们目前处在第三行。那么我们具有如下的情况： 目前第三行的状态为：01000（即我在2号上放了一个车），则前两行的合状态为00101（前两行里分别在3号和5号位置上放了车） 目前第三行的状态为：00100（即我在3号上放了一个车），则前两行的合状态为01001（前两行里分别在2号和5号位置上放了车） 目前第三行的状态为：00001（即我在5号上放了一个车），则前两行的合状态为01100（前两行里分别在2号和3号位置上放了车） 则我们定义f [ s ]为：在s串的状态下，一共可能的放置方案数目。 注意，s本身就携带着“阶段（行号）”和“状态”两层信息，所以动规数组 f 只用一维就可以了。 我们再用Xi表示以前行的所有可能的合状态（就是例子里我标蓝的部分，X1,X2,X3） 则有 f [ s ] = f [ X1 ] f [ X2 ] f [ X3 ] …… f [ Xi ]
那么如何实现是一个问题。我们有这个函数：lowbit ( x ) 如果不知道的话，可以百度。我在这里简单说几句 lowbit ( x ) 返回的是一个数x（二进制形式）中，最低位的1，与其后的所有0，组成的的数值。 举例一：100001110100111000 该数字的lowbit值为“1000”，即8 举例二：10001010 该数字的lowbit值为“10”，即2 举例三：1001 该数字的lowbit值为“1”，即1 实现方式
int lowbit(int x){return (x&(-x));}
为什么这么做可以？利用了负数使用补码储存的原理。具体的自己去百度吧。
使用lowbit函数，我们就可以使用这样的方式来统计，s数串里“1”的个数，以获取它所携带的行号信息：第“cnt”行 for(int i=s;i;i-=lowbit(i))cnt ;//当前是第cnt行
在执行那个标蓝部分，和动态转移的时候，我们使用这样一种巧妙的方式来进行寻找s所有子序列的工作 for(int i=s;i;i-=lowbit(i)){
if(!(a[cnt] & lowbit(i))){
int x=s^lowbit(i);
f[s] =f[x];
}
}
我们模拟一下：假设当前s串为“ 010110010” 那么开始：
i 记录：010110010；lowbit（i）=10，这个就是我们目前假设的本行车所在的位置。 “如果该行障碍 a [ cnt ]条件允许”，那么我们将原来s串010110010，中的“10“消去，变为010110000，记录为x。这个x就是之前行的合状态。 将 f [ s ] 加上这一种之前合状态的数目。
i 减去 10，i记录：010110000；lowbit ( i ) =10000，这个就是我们目前又假设的本行车所在位置的另一种情况。 “如果该行障碍 a [ cnt ]条件允许”，那么我们将原来s串010110010，中的“10000“消去，变为010100010，记录为x。这个x就是之前行的合状态。 将 f [ s ] 加上这一种之前合状态的数目。
i 减去 10000，i记录：010100000；lowbit ( i ) =100000，这个就是我们目前又假设的本行车所在位置的另一种情况。 “如果该行障碍 a [ cnt ]条件允许”，那么我们将原来s串010110010，中的“100000“消去，变为010010010，记录为x。这个x就是之前行的合状态。 将 f [ s ] 加上这一种之前合状态的数目。
i 减去 100000，i记录：010000000；lowbit ( i ) =10000000，这个就是我们目前又假设的本行车所在位置的另一种情况。 “如果该行障碍 a [ cnt ]条件允许”，那么我们将原来s串010110010，中的“10000000“消去，变为000110010，记录为x。这个x就是之前行的合状态。 将 f [ s ] 加上这一种之前合状态的数目。
i 减去10000000，i记录：0循环停止。 这时候 f [ s ] 就是本s串的答案了！
那么再提醒一个点。根据我之前写的那个玉米田的题，我们既然有n列，那么每一行就会有2^n -1种不同的s串 。 不同的是，由于我们这回首先预处理： f [ 0 ] =1，即一个不放也是一种情况，所以这回我们s串映射的就不再是0到2^n-1了，而是1到2^n 不过最后输出的时候，记得输出 f [ 2^n -1 ] 而且注意longlong的问题。数目比较大，使用longlong。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn=1<<20 1;
typedef long long ll;
ll f[maxn],a[25];//a记录行障碍状态
int lowbit(int x){return (x&(-x));}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i ){
int x,y;scanf("%d%d",&x,&y);
a[x] =(1<<(y-1));
}
f[0]=1;//一个不放也是一种方案
int maxs=1<<n;
for(int s=1;s<=maxs;s ){
int cnt=0;
for(int i=s;i;i-=lowbit(i))cnt ;//当前是第cnt行
for(int i=s;i;i-=lowbit(i)){
if(!(a[cnt] & lowbit(i))){
int x=s^lowbit(i);
f[s] =f[x];
}
}
}
printf("%lld\n",f[maxs-1]);
return 0;
}
祝AC 来源：https://www./content-4-677151.html |
|
|
