随笔 - 6  文章 - 1  trackbacks - 0
<2016年1月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Marcool四个国王解法
题目大意是:
在一个M×N的棋盘上,放置K个国王(注意!不是王后),有多少种互相不攻击的方法。
测试数据里面有:70%,1<=M<=5,1<=N<=5,1<=K<=10。这个数据量用广搜就能AC,麻烦的是剩下的是1<=M<=100,1<=N<=50,1<=K<=M*N,这就需要一些数学方法进行判断了。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX 2147483648
 4 using namespace std;
 5 int n, m, king_number;
 6 long long dp[100][1000], dp_tmp[100][1000], ans = 0;
 7 bool flag[10];
 8 void READY(int x)
 9 {
10     memset(flag, falsesizeof(flag));
11     int cnt = n;
12     while (x != 0)
13     {
14         if (x % 2 == 0)
15             flag[cnt] = true;
16         x /= 2;
17         cnt--;
18     }
19 }
20 void Deep_Fisrt_Search(int x, int y, int z, long long std_dp, bool left)
21 {
22     if (z > king_number)
23         return ;
24     if (x == n + 1)
25     {
26         dp_tmp[y][z] += std_dp;
27         if (dp_tmp[y][z] > 2147483647)
28             dp_tmp[y][z] = MAX;
29         return ;
30     }
31     Deep_Fisrt_Search(x + 1, y * 2, z, std_dp, false); 
32     if(! left && ! flag[x] && !(x - 1 >= 1 && flag[x - 1]) && ! (x + 1 <= n && flag[x + 1])) 
33         Deep_Fisrt_Search(x + 1, y * 2 + 1, z + 1, std_dp, true); 
34     return ;
35 }
36 int main()
37 {
38     scanf("%d %d %d"&n, &m, &king_number);
39     memset(dp, 0sizeof(dp));
40     dp[0][0= 1;
41     int end = 1;
42     for (int i = 1; i <= n; i++)
43         end *= 2;
44     end --;
45     for (int i = 1; i <= m; i++)
46     {
47         memset(dp_tmp, 0sizeof(dp_tmp));
48         for (int j = 0; j <= end; j++)
49         {
50             READY(j);
51             for (int k = 0; k <= king_number; k++)
52             {
53                 if (dp[j][k] == 0)
54                     continue;
55                 Deep_Fisrt_Search(10, k, dp[j][k], false);
56             }
57         }
58         memcpy(dp, dp_tmp, sizeof(dp)); 
59     }
60     for (int i = 0; i <= end; i++)
61     {
62         ans += dp[i][king_number];
63         if (ans > 2147483647)
64         {
65             printf("2147483648\n");
66             return 0;
67         }
68     }
69     printf("%lld\n", ans);
70     return 0;
71 }
72 
posted on 2012-10-04 11:29 某科学的魂魄妖梦 阅读(238) 评论(1)  编辑 收藏 引用

FeedBack:
# re: Marcool 海淀区区赛试题 四个国王 2016-01-08 20:55 renja
#include <stdio.h>
#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;
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理