比赛 |
exam |
评测结果 |
AAAAAAAAWW |
题目名称 |
放国王 |
最终得分 |
80 |
用户昵称 |
玉带林中挂 |
运行时间 |
0.037 s |
代码语言 |
C++ |
内存使用 |
5.07 MiB |
提交时间 |
2017-07-03 19:29:22 |
显示代码纯文本
#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;
}