AcWing 1064. 小国王
原题链接
简单
作者:
wangyj
,
2021-01-18 18:35:27
,
所有人可见
,
阅读 288
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
int n,m,cnt[1024];
vector<int>state,head[1024];
LL f[12][110][1024];
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,i;
for(i=0;i<n;i++)res+=state >> i & 1;
return res;
}
int main()
{
int i,j,a,b;
scanf("%d%d",&n,&m);
for(i=0;i< 1 << n;i++)if(check(i)){state.push_back(i);cnt[i] = count(i);}
for(i=0;i<state.size();i++)for(j=0;j<state.size();j++){
a=state[i],b=state[j];
if((a&b)==0&&check(a|b))head[i].push_back(j);
}
f[0][0][0]=1;
for(i=1;i<=n+1;i++)for(j=0;j<=m;j++)for(a=0;a<state.size();a++)
for (int b:head[a]){
int c=cnt[state[a]];
if(j>=c)f[i][j][a]+=f[i-1][j-c][b];
}
printf("%lld\n",f[n+1][m][0]);
return 0;
}