似乎該博弈了！（動態規劃），

題目來源：https://biancheng.love/contest-ng/index.html#/41/problems

F 似乎該博弈了！

題目描述

nova君陷入了困境，因為他無法在PS4游戲上憑借操作戰勝對手。機智如他，只好和對手博弈了！

nova君拿出的方案和以往有些不一樣，他說：“你可以決定石子數量和石子的取法，我來決定先後手，這樣非常公平。”他的對手覺得nova君說的有道理，於是不僅決定了每局的石子數量，還給出了k個數字，表示每次可以任意取走數量等同於這k個數字中一個的石子，k中一定有一個為1。先取完者為勝。

現在很急很關鍵，快幫nova君看看他到底應該先手還是後手才能戰勝對手。

輸入

每組測試數據兩行。

第一行兩個整數n和k，第二行k個整數，意義如題目描述。

N<=100000,k<=15

輸出

對於每組數據，輸出一行，為nova應該采取的先後手 sente \ gote

輸入樣例

4 3
1 2 3
1 1
1 

輸出樣例

gote
sente

解題思路：給定n個石頭，和k種去除石頭的方式，每種方式可以去除一定量的石頭， 現在Sente(簡稱S),gote(簡稱O)，S先手，O後手，每次每個人能選擇一種去除石頭的方式，誰去除最後一堆誰就贏了。要求出必勝之人是誰。
分析：
1.用一個dp數組記錄，對於先手者能取到的記錄為1，後手者為0.
2.初始dp數組都為0，遍歷1到n，如果dp[i]為0，說明上一手是後手取得，這樣先手就能取，把dp[i]變為1，由於是從1到n，這樣每個狀態記錄時，前面的都已經記錄好了，所以是可行的.
3.這樣最後只需要判斷dp[n]是1，還是0，就可以判斷是先手勝還是後手勝了。
狀態轉移方程為：if (i - mjmj[j] >= 0 && !dp[i - mjmj[j]])  dp[i] = 1.
給出代碼：

 1 #include <bits/stdc++.h>
 2 #define MAX 1000010
 3 int dp[MAX],mjmj[15];
 4 
 5 int n,m,i,j;
 6 int main()
 7 {
 8     while(~scanf("%d",&n))
 9     {
10         memset(dp,0,sizeof(dp));
11         scanf("%d",&m);
12         for (i=0; i<m; i++)
13         {
14             scanf("%d",&mjmj[i]);
15         }
16         for (i=1;i<=n;++i)
17         {
18             for (j=0;j<m;++j)
19             {
20                 if (i-mjmj[j]>=0&&!dp[i-mjmj[j]])
21                 {
22                     dp[i]=1;
23                     break;
24                 }
25             }
26         }
27         if (dp[n])
28             printf("sente\n");
29         else
30             printf("gote\n");
31     }
32     return 0;
33 }

推薦博客：http://blog.csdn.net/kjc19920531/article/details/8120989

推薦博客：http://blog.csdn.net/wangtaoking1/article/details/7308117