AcWing 1064. 小国王
原题链接
简单
作者:
_cc
,
2022-01-26 14:48:50
,
所有人可见
,
阅读 214
状态压缩DP
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=15,M=1<<10;
vector<int> state; //存所有合法状态
vector<int> head[M]; //存当前状态可以和哪个状态相互转移
long long f[N][105][M]; //f[i][j][s]:已经摆完了前i行,已经选了j个国王,并且当前状态是s
int n,m;
bool check(int x){ //求当前状态是否有连续的1
for(int i=0;i<n;i++){
if((x>>i&1) && (x>>(i+1)&1)) return false;
}
return true;
}
int count(int x){ //求当前状态有多少个1
int res=0;
for(int i=0;i<n;i++){
if(x>>i&1) res++;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<(1<<n);i++){ //枚举所有状态是否合法
if(check(i)){
state.push_back(i);
}
}
for(int i=0;i<state.size();i++){
for(int j=0;j<state.size();j++){
auto a=state[i],b=state[j];
if((a&b)==0 && check(a|b)){ //a&b==0:上下两行没有并列的国王能攻击到。check(a|b):斜方向没有国王能攻击到
head[i].push_back(j); //i状态和j状态可以相互转移
}
}
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<state.size();k++){
for(vector<int>::iterator iter = head[k].begin(); iter != head[k].end(); iter++){
//枚举当前状态可以由哪些状态转移到
int c=count(state[k]); //当前状态有多少个1(代表有多少个国王)
if(j>=c){
f[i][j][k]+=f[i-1][j-c][*iter]; //状态转移
}
}
}
}
}
/*
上面枚举状态也可以写成这样
for(auto l:head[k]){
//枚举当前状态可以由哪些状态转移到
int c=count(state[k]); //当前状态有多少个1(代表有多少个国王)
if(j>=c){
f[i][j][k]+=f[i-1][j-c][l];
}
}
*/
cout<<f[n+1][m][0]<<endl;
//这是前面的定义:f[i][j][s]:已经摆完了前i行,已经选了j个国王,并且当前状态是s
//f[n+1][m][0]已经摆完了前n+1行,并且已经选了m个国王,但是这个状态是0(状态是0说明我们没有选)
//所以想当是已经摆完了前n+1行,并且已经选了m个国王,并且第n+1行没有选
//所以f[n+1][m][0]==f[n][m][s]
return 0;
}