HDU 1847 Good Luck in CET-4 Everybody!(巴什博弈论) - c++编程基础

TOP

HDU 1847 Good Luck in CET-4 Everybody!(巴什博弈论)

2015-07-20 17:40:51 来源: 作者: 【大中小】浏览:3次

Tags：HDU 1847 Good Luck CET-4 Everybody 巴什博弈论

题目地址：HDU 1847

这题可以用NP状态转换。

首先0的时候就代表无法出牌了，所以是必败态。然后根据每一个可以一步到达必败态的是必胜态，不可以一步到达必败态的是必败态。可以推出状态转移方程，然后用DP求解。即从已知状态向未知状态转移，就是从小的向大的转移，假如它的下一步没有必败态，则它是必败态，若下一步有一个必败态，那它就是必胜态。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; int dp[2000], a[100]; int main() { int n, i, j, m, flag; a[0]=1; for(i=1;; i++) { a[i]=a[i-1]*2; if(a[i]>1000) { m=i; break; } } dp[0]=0; for(i=1;i<=1000;i++) { flag=0; for(j=0;j
             
              i) break; if(!dp[i-a[j]]) { flag=1; break; } } if(flag) dp[i]=1; else dp[i]=0; } while(scanf("%d",&n)!=EOF) { if(dp[n]) puts("Kiki"); else puts("Cici"); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU5011：Game（博弈）	下一篇：UVa10054 The Necklace，无向图求..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: