C++博客-某科学的魂魄妖梦的笔记-最新评论http://www.cppblog.com/youmukonpaku/CommentsRSS.aspxC++/C#/Java均可 DirectX/OpenGL也okzh-cnThu, 04 Oct 2012 04:27:00 GMTThu, 04 Oct 2012 04:27:00 GMTcnblogsre: Marcool 海淀区区赛试题 四个国王http://www.cppblog.com/youmukonpaku/archive/2016/01/08/192752.html#212632renjarenjaFri, 08 Jan 2016 12:55:00 GMThttp://www.cppblog.com/youmukonpaku/archive/2016/01/08/192752.html#212632#include <string.h>
#define MAX 2147483648
using namespace std;
int n, m, king_number;
long long dp[100][1000], dp_tmp[100][1000], ans = 0;
bool flag[10];
void READY(int x)
{
memset(flag, false, sizeof(flag));
int cnt = n;
while (x != 0)
{
if (x % 2 == 0)
flag[cnt] = true;
x /= 2;
cnt--;
}
}
void Deep_Fisrt_Search(int x, int y, int z, long long std_dp, bool left)
{
if (z > king_number)
return ;
if (x == n + 1)
{
dp_tmp[y][z] += std_dp;
if (dp_tmp[y][z] > 2147483647)
dp_tmp[y][z] = MAX;
return ;
}
Deep_Fisrt_Search(x + 1, y * 2, z, std_dp, false);
if(! left && ! flag[x] && !(x - 1 >= 1 && flag[x - 1]) && ! (x + 1 <= n && flag[x + 1]))
Deep_Fisrt_Search(x + 1, y * 2 + 1, z + 1, std_dp, true);
return ;
}
int main()
{
scanf("%d %d %d", &n, &m, &king_number);
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int end = 1;
for (int i = 1; i <= n; i++)
end *= 2;
end --;
for (int i = 1; i <= m; i++)
{
memset(dp_tmp, 0, sizeof(dp_tmp));
for (int j = 0; j <= end; j++)
{
READY(j);
for (int k = 0; k <= king_number; k++)
{
if (dp[j][k] == 0)
continue;
Deep_Fisrt_Search(1, 0, k, dp[j][k], false);
}
}
memcpy(dp, dp_tmp, sizeof(dp));
}
for (int i = 0; i <= end; i++)
{
ans += dp[i][king_number];
if (ans > 2147483647)
{
printf("2147483648\n");
return 0;
}
}
printf("%lld\n", ans);
return 0;
}

renja 2016-01-08 20:55 发表评论
]]>