信息
- ID
- 486
- 时间
- 500ms
- 内存
- 64MiB
- 难度
- 3
- 标签
- 递交数
- 38
- 已通过
- 22
- 上传者
状态压缩动规
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#define int long long
using namespace std;
const int N=(1<<11);
const int INF=0x3f3f3f3f;
int dp[12][N][100],check[N];
int n,m;
void init(){
for(int i=0;i<(1<<n);i++){
int x=i;
while(x>0){
check[i]++;
x-=x&(-x);
}
}
}
signed main(){
cin >> n >> m;
init();
for(int i=0;i<(1<<n);i++){
dp[1][i][check[i]]=1;
}
for(int le=2;le<=n;le++){
for(int i=0;i<(1<<n);i++){
if(i&(i<<1))continue;
for(int j=0;j<(1<<n);j++){
if((j&(j<<1))||(i&j)||(i&(j<<1))||(i&(j>>1)))continue;
for(int k=check[i];k<=m;k++){
dp[le][i][k]+=dp[le-1][j][k-check[i]];
}
}
}
}
int ans=0;
for(int i=0;i<(1<<n);i++){
ans+=dp[n][i][m];
}
cout << ans;
return 0;
}