HOJ-2662Pieces Assignment(状态压缩，动态规划)

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
long long int dp[85][1<<10][25];//在第i行，棋子为k个，状态为s的状态数
int n,m,k;
int getsum(int x)
{
        int res=0;
    int i=0;
        while(x)
        {
                if(res&&(x&1))
                        return -1;
                if(res=(x&1))
                        i++;
                x>>=1;
        }
        return i;
}
int main()
{
        while(scanf("%d%d%d",&n,&m,&k)!=EOF)
        {
                //根据n,m的大小确定行和列
                if(n<m)
                        swap(n,m);
                memset(dp,0,sizeof(dp));
                dp[0][0][0]=1;
                int end=(1<<m)-1;
                for(int i=1;i<=n;i++)
            {
                    for(int p=0;p<=k;p++)
                    {
                          for(int j=0;j<=end;j++)
                              {
                                          int t=getsum(j);
                                          if(t==-1||t>p)
                                                  continue;
                                          for(int v=0;v<=end;v++)
                                          {
                                                  if(getsum(v)==-1||(v&j))
                                                          continue;
                                                  dp[i][j][p]+=dp[i-1][v][p-t];

                                          }


                              }
                        }

                }
                long long int sum=0;
                for(int i=0;i<=end;i++)
             sum+=dp[n][i][k];
                printf("%lld\n",sum);

        }