【题目描述】
http://www.lydsy.com/JudgeOnline/problem.php?id=1087
【题解】
状压dp不解释
/* --------------
user Vanisher
problem bzoj-1087
----------------*/
# include <bits/stdc++.h>
# define ll long long
# define inf 0x3f3f3f3f
# define N 11
using namespace std;
ll read(){
ll tmp=0, fh=1; char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
return tmp*fh;
}
ll f[N][N*N][1<<N],cnt[1<<N],n,m,ans,f1[N],f2[N];
bool mp[1<<N][1<<N];
bool check(ll i1, ll i2){
for (ll i=1; i<=n; i++)
f1[i]=(((1<<(i-1))&i1)!=0),
f2[i]=(((1<<(i-1))&i2)!=0);
for (ll i=1; i<=n; i++)
if (f1[i]){
if (f2[i]!=0||f2[i-1]!=0||f2[i+1]!=0)
return 0;
}
for (ll i=2; i<=n; i++)
if (f1[i]&&f1[i-1]||f2[i]&&f2[i-1])
return 0;
return 1;
}
int main(){
n=read(), m=read();
f[0][0][0]=1;
for (ll i=1; i<(1<<n); i++)
cnt[i]=cnt[i/2]+i%2;
for (ll i=0; i<(1<<n); i++)
for (ll j=0; j<(1<<n); j++)
mp[i][j]=check(i,j);
for (ll i=1; i<=n; i++){
for (ll k=0; k<(1<<n); k++){
ll j=cnt[k];
for (ll t=j; t<=m; t++){
for (ll p=0; p<(1<<n); p++){
if (mp[p][k]==1)
f[i][t][k]=f[i][t][k]+f[i-1][t-j][p];
}
}
}
}
for (ll i=0; i<(1<<n); i++)
ans=ans+f[n][m][i];
printf("%lld
",ans);
return 0;
}