UVA10404 Bachet's Game - c++编程基础

这题目做的有些较劲，题意：给你n个石头，Stan跟Ollie按顺序取，Stan先手，题目会给你m种取法，每次取石头的数目必须从这m种中选取一个，假设Stan 和 Ollie 每次的取石头数目都是最完美的意思就是输赢一开始就因为取法和石头数目决定了，不会因为人为原因而影响结果

这题目一看，个人认为是一道博弈的问题，所以开始较劲了，各种寻找sg值的方法，不停的去推去寻找必败点必胜点，做到后面发现不对劲，每次取石头取好以后，当前剩余石头都会有一个固定的状态，以Stan为基准，那么这里0表示Stan必输，1表示Stan必胜，肯定是有这两个状态的，从当前剩余0个石头的状态推到当前剩余n的状态，就知道结果了，这样以剩余0为边界条件来dp试试看，最后寻找到了状态转移方程

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                //#define ll long long #define ll __int64 #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int num[12]; int dp[1000000 + 5]; void clear() { memset(num,0,sizeof(num)); memset(dp,0,sizeof(dp)); } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2) { clear(); for(int i=0;i
                    
                     = num[j] && dp[i - num[j]] == 0) { dp[i] = 1;break; } } } if(dp[n]) puts("Stan wins"); else puts("Ollie wins"); } return EXIT_SUCCESS; }