加载中…
个人资料
catcherpan
catcherpan
  • 博客等级:
  • 博客积分:0
  • 博客访问:10,802
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

hdu 4111 Alice and Bob

(2011-11-10 19:06:20)
标签:

杂谈

分类: 博弈

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4111

 

     成都站现场赛的A题。。。。。。

     如果没有1,则只有两种操纵:1、减1; 2、相加。。。。。总步数是一定的,但去掉一个1相当于操纵了两次。。。。。。。。

     关键是要把握好处理值为1的数字,于是定义:dp[i][j]:  0:Alice胜 1:Alice败。。。。。。

其中 i:1的个数 

     j:合并非1队要的次数

 

其实它的核心思想还是:由必败点找必胜点。。。。。只不过是通过dp的途径找的。。。。。。。。。

 

代码:

01 #include <iostream>
02 #include <cstring>
03 using namespace std;
04
05 int dp[55][60000];
06
07 int DP(int i,int j)
08 {
09     if(dp[i][j]!=-1)
10         return dp[i][j];
11     if(j==1)
12         return dp[i][j]=DP(i+1,0);
13
14     dp[i][j]=0;
15     if(i>=1 && !DP(i-1,j))  //擦掉一个1
16         dp[i][j]=1;
17     else if(j>=1 && !DP(i,j-1)) //将大于1的数减1
18         dp[i][j]=1;
19     else if(i>=1&&j>0&&!DP(i-1,j+1)) //将一个1加到大于1的数上
20         dp[i][j]=1;
21     else if(i>=2&& ((j>=1&&!DP(i-2,j+3))||(j==0&& !DP(i-2,2))))  //将两个1相加
22         dp[i][j]=1;
23
24     return dp[i][j];
25 }
26
27 void main()
28 {
29     int icase,i,j,k,n,t;
30     cin>>icase;
31     memset(dp,-1,sizeof(dp));
32     for(i=1;i<=icase;i++)
33     {
34         j=0;
35         k=0;
36         cin>>n;
37         while (n--)
38         {
39             cin>>t;
40             if(t==1)
41                 j++;
42             else
43                 k+=(t+1);
44         }
45         if(k)
46             k--;
47         cout<<"Case #"<<i<<": ";
48         if(DP(j,k))
49             cout<<"Alice"<<endl;
50         else
51             cout<<"Bob"<<endl;
52     }
53 }

 

 

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有