emm 为什么题解区大佬都不愿意用状压啊……
看到这题的数据范围:
- 对于 $100 \%$ 的数据,保证 $n \leq 18$。
而众所周知,int
类型的变量可以存储 32 位带符号整数(去除符号位共 31 位)。也就是说,在这题中,我们甚至不需要 long long
就能将题目中方阵的一行塞到一个变量里(状态压缩)。
思路和其他几篇题解大致相同,但是貌似细节上还是不太一样,并且我的码量介于题解区另外两位大佬之间。
思路简述:
- 枚举第一行可能出现的所有状态(状态压缩)
- 对于每一种状态:
- 验证其是否合法,若其不合法则直接进入下一种状态
- 若其合法,则使用一个循环,数出从原方阵的第一行转移到此状态所需要的步骤
- 对其进行深度优先搜索:
- 根据传入的状态推导出下一行(程序里有详细过程)
- 在下一行重复此过程
对于这个思路,我们需要考虑一个问题:什么样的状态是不合法的?
很显然,题目中有明确表述,女生可以改♂成男生,但是男生不能改♂成女生。(女拳震怒
还是结合程序说实际一些:
//Luogu-P1391
//Luogu @Enterpr1se (Userid 363523)
//@_Qijia (Userid 363524) AK IOI!
#include<cstdio>
#define regll register long long
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
_Qijia AK IOI;
int n,mp[20],temp,ans=0x7fffaded,sstep;
bool flag;
int bin_digit(int num,int id){//获取一个二进制数的第 id 位(最低位为第0位)
return ((num&(1<<id))>>id);
}
int min(int a,int b){
return a<b?a:b;
}
void dfs(int id,int currln,int curstep,int prevln=0){
if(id==n){//如果已经扫过整个方阵,并且没有出现不合法状态
ans=min(ans,curstep);//更新答案
return;
}
int surmal/*一个人周围已有的男生数*/,nextln=0/*下一行的状态*/,nstep=0/*到下一行为止总共的换人次数*/;
for(regint i=1;i<=n;++i){
surmal=bin_digit(currln,i-1)+bin_digit(currln,i+1)+bin_digit(prevln,i);//一个人周围的总男生数 = 左边 + 右边 + 上一行同一位置男生数
nextln+=((surmal&1)<<i);//更新状态(将新一位加入到下一行的状态中)
if((bin_digit(mp[id+1],i)^bin_digit(nextln,i))){//如果下一行该位置需要的人与原方阵中此位置的人性别不同
++nstep;//增加一次换人
if(bin_digit(mp[id+1],i))/*若原方阵中此位置是男生*/ return;
}
}
dfs(id+1,nextln,curstep+nstep,currln);//从下一行开始搜索
return;
}
signed main(){
scanf("%d",&n);
for(regint i=1;i<=n;++i)
for(regint j=1;j<=n;++j,mp[i]<<=1)
scanf("%d",&temp),mp[i]+=temp;//将新输入的一位加在末尾
for(regint i=0;i<(1<<(n+1));i+=2){//枚举第一行所有状态
sstep=0;//初始化
flag=true;
for(regint j=1;j<=n;++j){//检查状态是否合法 并 算出第一行换人次数
if((bin_digit(mp[1],j)^bin_digit(i,j))){//类似于 Ln29 至 Ln32
++sstep;
if(bin_digit(mp[1],j)){
flag=false;
break;
}
}
}
if(flag) dfs(1,i,sstep);//如果状态合法
}
printf("%d",((ans^0x7fffaded)?ans:-1));
return 0;
}
注:这题的状压看着有些奇怪,因为我决定将二进制数的最低位留空(永远为 0),这样在获取二进制数某一位的时候更加方便。例如样例中第二行,在本程序中存储为 $ 1000_2 $。
$\mathtt{Thanks}\text{ }\mathtt{for}\text{ }\mathtt{reading.}\text{ }$