bzoj1087

洛谷P1896

想了很久,太久没做状压都已经不会了。。。

状压每一行就好了

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n,K,s;
ll an[][][],ans;
bool ok[];
int pcnt[];
#define in(a,b) (((a)&(b))==(a))
vector<int> son[];
int main()
{
int i,j,k,l1,l,t;
scanf("%d%d",&n,&K);s=(<<n)-;
for(i=;i<=s;++i)
ok[i]=!((i&(i<<))|(i&(i>>)));
for(i=;i<=s;++i)
pcnt[i]=__builtin_popcount(i);
for(i=;i<=s;++i)
if(ok[i])
{
t=s&(~(i|(i<<)|(i>>)));
for(j=t;j;j=(j-)&t)
if(ok[j]&&in(i,s&(~(j|(j<<)|(j>>)))))
{
//printf("1t%d %d\n",i,j);
son[i].pb(j);
}
son[i].pb();
}
for(i=;i<=s;++i)
an[][pcnt[i]][i]=;
for(i=;i<=n;++i)
{
for(j=;j<=K;++j)
{
for(k=;k<=s;++k)
if(ok[k]&&pcnt[k]<=j)
{
for(l1=;l1<son[k].size();++l1)
{
l=son[k][l1];
//printf("3t%d %d\n",j-pcnt[k],l);
an[i][j][k]+=an[i-][j-pcnt[k]][l];
}
//printf("2t%d %d %d %lld\n",i,j,k,an[i][j][k]);
}
}
}
for(i=;i<=s;++i)
ans+=an[n][K][i];
printf("%lld",ans);
return ;
}
04-28 12:51