比赛 |
动规 |
评测结果 |
AAAAAAAAAA |
题目名称 |
放国王 |
最终得分 |
100 |
用户昵称 |
TARDIS |
运行时间 |
0.015 s |
代码语言 |
C++ |
内存使用 |
5.34 MiB |
提交时间 |
2017-06-18 21:33:08 |
显示代码纯文本
#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=15,maxk=1<<10;
long long f[maxn][maxk][maxn*maxn],s[maxk],cnt[maxk],t;
long long n,k,temp;
inline void in(){
#ifdef COGS
freopen("placeking.in","r",stdin);
freopen("placeking.out","w",stdout);
#endif
scanf("%d%d",&n,&k);
temp=(1<<n)-1;
}
inline void dfs(int cur,int ss){
if (cur==n){
s[++t]=ss;
return;
}
dfs(cur+1,ss<<1);
if(!(ss&1)) dfs(cur+1,(ss<<1)+1);
}
inline void init(){
f[0][0][0]=1;
for (int i=0;i<=temp;i++){
cnt[i]=cnt[i>>1]+(i&1);
}
for (int i=1;i<=t;i++){
f[1][i][cnt[s[i]]]=1;
}
}
inline bool check(int s1,int s2){
if ((s[s1]&s[s2])||(s[s1]&(s[s2]<<1))||(s[s1]&(s[s2]>>1))) return 0;
else return 1;
}
inline void dp(){
for (int i=1;i<=n;i++){
for (int j=0;j<=k;j++){
for (int y=1;y<=t;y++){
for (int q=1;q<=t;q++){
if (check(y,q)&&j>=cnt[s[y]]){
f[i][y][j]+=f[i-1][q][j-cnt[s[y]]];
}
}
}
}
}
}
inline void deal(){
dfs(0,0);
init();
dp();
}
inline void out(){
long long ans=0;
for (int i=0;i<=t;i++){
ans+=f[n][i][k];
}
printf("%lld",ans);
}
int Main(){
in();
deal();
out();
return 0;
}
int main(){;}
int xlm=Main();