bzoj1087

题解：
状压dp
代码：
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

int n,m,cnt[N],c1[N],c2[N][N];

ll ans,f[][N][N];

void pre()

{

    int s;

    for (int i=;i<<<n;i++)

     if ((i&(i>>))==)

      {

        s=;

        for (int x=i;x;x>>=)s+=(x&);

        cnt[i]=s;c1[i]=;

      }

    for (int i=;i<<<n;i++)

     if (c1[i])

      for (int j=;j<<<n;j++)

       if (c1[j])

        if (((i&j)==)&&((i&(j>>))==)&&((j&(i>>))==))c2[i][j]=;

}

int main()

{

    scanf("%d%d",&n,&m);

    pre();

    for (int i=;i<<<n;i++)

     if (c1[i])f[][cnt[i]][i]=;

    for (int j=;j<n;j++)

     for (int k=;k<<<n;k++)

      if (c1[k])

       for (int i=;i<<<n;i++)

        if (c1[i])

         if (c2[k][i])

          for (int p=cnt[k];p+cnt[i]<=m;p++)f[j+][p+cnt[i]][i]+=f[j][p][k];

    ll ans=;

    for (int i=;i<<<n;i++)ans+=f[n][m][i];

    printf("%lld",ans);

    return ;

}
相关文章
