首页 > 代码库 > 摆棋子

摆棋子

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>

using namespace std;

long long n,m,k,dp[82][22][1<<9],ans,mm;

long long mark[1<<9],len;

using namespace std;

long long num(long long x)

{

long long sum=0;

while(x)

{

if(x&1==1)

sum++;

x=x>>1;

}

return sum;

}

bool judge(long long x)

{

 

if(x&(x<<1)) return false;

return true;

}

int main()

{

while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF)

{

      ans=0;

      memset(dp,0,sizeof(dp));

      memset(mark,0,sizeof(mark));

      len = 0;

      long long tmpp = n > m ? n : m;

      m = n > m ? m : n;

      n = tmpp;

for(long long i=0;i<(1<<m);i++)

if(judge(i))

             {

dp[1][num(i)][len]=1;

mark[len ++] = i;

             }

for(long long i=2;i<=n;i++)

for(long long j=0;j<=k;j++)

for(long long x = 0 ; x < len ; x ++)

{

for(long long y = 0 ; y < len ; y ++)

{

     long long tmp = num (mark[x]);

if(((mark[x] & mark[y]) == 0 ) && j >= tmp)

dp[i][j][x] += dp[i - 1][j - tmp][y];

}

}

      for(long long i=0;i< len;i++)

            ans += dp[n][k][i];

      printf("%lld\n",ans);

}

return 0;

}

摆棋子