AcWing 1064. 小国王--一刷提高课!!!
原题链接
简单
作者:
月亮供电不足
,
2022-04-26 22:13:01
,
所有人可见
,
阅读 101
C++ 代码
/*
棋盘式状态压缩dp:
f[i,j,s]:
状态表示:
集合:前i行已经做完了,当前已经放了j个国王,且最后一行的状态是s的总方案数
属性:count-->方案数量
状态计算:
依据上一层的状态是什么(2^m种,从中挑取满足能放国王条件的情况进行状态转移)
假设第i-1行的状态是a,第i行的状态是b
第i-1行能放国王的条件是:
(1)第i-1行不能存在两个国王相邻
(2)第i-1行和第i行的国王不能相互攻击到
(a&b)==0(同一列不能有两个1) 且 a|b不能有相邻的1
f[i][j][a]-->
前i行已经摆放完毕,当前已经摆好了j个国王,第i行的状态是a
f[i-1][j-count(a)][b](所有合法的b)-->count(a)是第i行的状态a中1的个数(即第i行摆了多少个国王)
前i-1行已经摆放完毕,当前已经摆好了j-count(a)个国王,第i-1行的状态是b
f[i][j][a]=所有合法的b相加(f[i-1][j-count(a)][b])
具体代码实现时候的步骤:
(1)state预处理出所有的合法状态(一行没有两个相邻的1)-->放入vector<int>state中,
以及能够转移到这些合法状态的状态(即满足上面第i-1行能放国王的两个条件的)-->
能转移到某个合法状态的状态放入vector<int> head中
写好
1.check()函数判断state状态是否有两个相邻的1
2.count()函数计算出一个state状态中有多少个1-->cnt[state]每个合法状态中的1数量放进cnt数组中
(2)初始化f[0][0][0]=1;//什么都没摆放,是一种方案
遍历所有行数(1-->n+1)这里到n+1的原因是因为f[n+1][k][0]就表示前i+1行都摆好了
且第i+1行什么都没摆(相当于前i行摆好了k个国王),就是要求的结果
枚举摆放国王的数量(j->0--k>)
从所有合法的状态state中枚举所有第i行的状态a(j-count(a)>=0才行)
从所有能转移到state的状态中枚举第i-1行的状态b
(3)状态转移计算f[i][j][a]=所有合法的b相加(f[i-1][j-count(a)][b])
最后输出结果f[n+1][k][0]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1<<10;
LL f[12][110][N];
vector<int> state;
vector<int> head[N];
int cnt[N];//每种合法状态有多少个1
int n,k;
bool check(int s)//判断s是否是一个合法状态,不存在相邻的1
{
for(int i=0;i<n;i++)
{
if((s>>i & 1) && (s>>(i+1) & 1))return false;
}
return true;
}
int count(int s)//数一个状态内有多少个1,即摆了多少国王
{
int cnt=0;
for(int i=0;i<n;i++)
{
if(s>>i & 1) cnt++;
}
return cnt;
}
int main()
{
cin>>n>>k;
for(int i=0;i<1<<n;i++)
{
if(check(i))
{
state.push_back(i);
cnt[i]=count(i);
}
}
for(int i=0;i<state.size();i++)
{
for(int j=0;j<state.size();j++)
{
if((state[i]&state[j])==0 && check(state[i]|state[j]))
{
head[i].push_back(j);//i可以从j状态转移过来
}
}
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)//枚举第i行
{
for(int j=0;j<=k;j++)//枚举填了多少个国王
{
for(int a=0;a<state.size();a++)
{
for(auto b:head[a])
{
int u=cnt[state[a]];
if(j>=u)
{
f[i][j][state[a]]+=f[i-1][j-u][state[b]];
}
}
}
}
}
cout<<f[n+1][k][0];
return 0;
}