AcWing 1064. 小国王(棋盘式状压dp,重点:提前打表减小遍历范围)
原题链接
简单
作者:
逸误
,
2024-04-09 19:53:04
,
所有人可见
,
阅读 6
//棋盘式状压dp典题
//dp的时间复杂度公式:遍历所有元素的复杂度*每个元素的状态划分数
//重点:如果直接像上面所说遍历所有状态,会超时,而且每次还要判断状态是否合法,合法才将其作为一种状态划分加到dp数组
//这里预处理了state和head[M],存所有一行内的合法状态数和每个状态可以合法转移到的所有状态,然后就可以大大减少遍历广度!
//状态表示:f[i][j][s]:放好了前i行,一共放了j个国王,第i行的状态是s的所有方案
//属性:状态数
//状态划分:设s中有,对于每个f[i][j][s],可以划分为所有合法的且和上一行不相互攻击的方案数之和
//f[i][j][a]=Σ(f[i-1][j-count(last)][b])(所有合法方案之和)
//对于本行内就会相互攻击到的,不要去遍历,否则费时间,先处理出来同一行合法的全部方案(打表)
#include <iostream>
#include <vector>
using namespace std;
const int N = 12, M = 1<<10, K = 105;
typedef long long LL;
int n,m;
vector<int> state;//存所有同一行内的合法状态,遍历行用
vector<int> head[M];//存每个状态可以合法转移到的所有状态
int id[M];//存每个状态和下标之间的映射关系
int cnt[M];//存每个状态里1的个数(先打表)
LL f[N][K][M];//dp数组
bool check(int st)
{
return !(st&(st>>1));
}
int count(int st)
{
int res=0;
while(st)
{
res+=st&1;
st>>=1;
}
return res;
}
int main()
{
cin>>n>>m;
//打表state容器
for(int i=0;i<1<<n;i++)
if(check(i))
{
state.push_back(i);
id[i]=state.size()-1;//id将i映射到state中的下标
cnt[i]=count(i);//预处理i的1个数
}
for(auto &a:state)
for(auto &b:state)//遍历两行状态,j是上一排
{
if((a&b)==0&&check(a|b))//没有同一列和相邻列的1
{
head[a].push_back(b);//a可以转移到b,将b加入head[a]
}
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)
for(auto &a:state)
for(auto &b:head[a])//所有可以转移到a的状态
for(int j=0;j<=m;j++)
{
int c=cnt[a];//a有几个0
if(c<=j)
{
f[i][j][a]+=f[i-1][j-c][b];//由于有前面的打表,这里转移很方便,不用判断矛盾
//即前面打的表使这里每次遍历都是合法的一种状态划分,加上即可
}
}
//答案需要第n行所有m匹马状态之和,即f[n+1][m][0]
cout<<f[n+1][m][0]<<endl;
return 0;
}