比赛 |
状态压缩DP练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
放国王 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.226 s |
代码语言 |
C++ |
内存使用 |
22.25 MiB |
提交时间 |
2019-05-28 19:39:13 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,k,f[11][1<<10][100],sum;
int ju(int x,int y){
sum=0;
for(int i=1;i<=n;i++){
if(x>>(i-1)&1){sum++;
if((y>>(i-1))&1)return 0;
if((y>>(i))&1)return 0;
if((y>>(i-2))&1)return 0;
if((x>>(i-2))&1)return 0;
if((x>>(i))&1)return 0;
}
}
return 1;
}
int main(){
freopen("placeking.in","r",stdin);
freopen("placeking.out","w",stdout);
scanf("%lld%lld",&n,&k);
f[0][0][0]=1;
for(int a=1;a<=n;a++)
for(int i=0;i<=(1<<n)-1;i++)
for(int j=0;j<=(1<<n)-1;j++)
if(ju(i,j))
for(int p=0;p<=k-sum;p++)
f[a][i][p+sum]+=f[a-1][j][p];
sum=0;
for(int i=0;i<=(1<<n)-1;i++)sum+=f[n][i][k];
printf("%lld",sum);
return 0;
}