AcWing 1064. 小国王——(详细注释)
原题链接
简单
作者:
鲸_落
,
2020-11-04 21:20:28
,
所有人可见
,
阅读 592
个人总体感受,状压dp最重要的就是理解了状态转移,如何用二进制来表示,这道题自己也是看了很久吧,把自己的想法和思路都注释在下面代码里面了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=12,M=1<<10,K=120;
int n,m;
vector<int>state;
int count_one[M];
vector<int>head[M];
ll f[N][K][M];
bool check(int state)
{
for(int i=0;i<n;i++)
{
if((state>>i & 1) && (state>>i+1 & 1))
return false;
}
return true;
}
int count(int state)
{
int res=0;
for(int i=0;i<n;i++)
{
if(state>>i & 1) res++;
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=0;i<1<<n;i++)
{
if(check(i)) state.push_back(i);
count_one[i]=count(i);
}
for(int i=0;i<state.size();i++)
{
for(int j=0;j<state.size();j++)
{
int a=state[i],b=state[j];
if(check(a | b) && (a & b)==0) head[a].push_back(b);
}
}
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++)
{
int p=state[k];
for(int z=0;z<head[p].size();z++)
{
int h=head[p][z];
if(j>=count_one[p])
{
f[i][j][p]+=f[i-1][j-count_one[p]][h];
}
}
}
}
}
cout<<f[n+1][m][0]<<endl;
}