记录编号	418035	评测结果	AAAAAAAAWW
题目名称	放国王	最终得分	80
用户昵称	玉带林中挂	是否通过	未通过
代码语言	C++	运行时间	0.032 s
提交时间	2017-06-29 08:33:18	内存使用	5.63 MiB

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MID(x,y) ((x+y)>>1)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const int sup = 0x7fffffff;
const int inf = -0x7fffffff;

int n, k;
const int NUM_OF_PLACEMENGT = 520;
int s[NUM_OF_PLACEMENGT], c[NUM_OF_PLACEMENGT], place_num;         //每行的位置 
long long dp[13][NUM_OF_PLACEMENGT][103];

void dfs(int p, int condition_num, int condition_one_amount)
{             //存储每一行的位置
    if (p == n)
	{
        s[++ place_num] = condition_num;
        c[place_num] = condition_one_amount;
        return ;
    }
    dfs(p+1, condition_num << 1, condition_one_amount);
    if (!(condition_num & 1))
        dfs(p+1, condition_num << 1 | 1, condition_one_amount + 1);
    return ;
}
bool ifok(int s1, int s2)
{      //决定当前的状况和最后的条件是否为综合考虑。
    if(s1 & s2) return false;         //和正上方判断
    if(s1 & (s2<<1))return false;     //和右上方判断
    if(s1 & (s2>>1))return false;     //和左上方判断
    return true;
}
int main()
{
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);    	
	while(scanf("%d %d", &n, &k) != EOF)
	{
      	mem(dp, 0);
       	place_num = 0;
       	dp[0][1][0] = 1;
       	dfs(0, 0, 0);
       	for (int i = 1; i <= n; i ++)
		{
          	for (int j1 = 1; j1 <= place_num; j1 ++)
			{
                for (int j2 = 1; j2 <= place_num; j2 ++)
				{
                    for (int w = 0; w <= k; w ++)
					{
                 	       if (ifok(s[j1], s[j2]) && w-c[j1] >= 0)
                         dp[i][j1][w] += dp[i-1][j2][w-c[j1]];
               	     }
            	}
           	}
       	}
       	long long res = 0;
       	for (int j = 1; j <= place_num; j ++)
        res += dp[n][j][k];
       	printf("%I64d\n", res);
    }
    fclose(stdin);fclose(stdout);
	return 0;
}