Description

Sample Input

5 5 5

Sample Output

4

Solution

其實(shí)這題就是一個(gè)博弈DP，但是我們考慮怎么設(shè)計(jì)DP狀態(tài)使我們可以用這些DP狀態(tài)表示所有博弈狀態(tài)。

我們發(fā)現(xiàn)會(huì)對(duì)局面造成影響的有第一局面的取法和第二局面的堆數(shù)，石子個(gè)數(shù)什么的。

那么又綜合上博弈DP的狀態(tài)特點(diǎn)設(shè)計(jì)出一個(gè)狀態(tài)
：
\(f[i][j]\) 表示第一局面還剩下 \(i\) 個(gè)石子，第二局面的 \(SG\) 值為 \(j\) 時(shí)當(dāng)前要操作的人是負(fù)還是勝。

轉(zhuǎn)移時(shí)我們只要枚舉當(dāng)前選多少石子拿到第二局面。

那么怎么轉(zhuǎn)移。

有一個(gè)狀態(tài)并且這個(gè)狀態(tài)的后繼中有負(fù)的狀態(tài)那么當(dāng)前狀態(tài)就是必贏。

#include<bits/stdc++.h> using namespace std;int n,p,K; const int N=1005,P=1007,M=1034; int f[N][M];inline int SG(int x){if(x<=1) return x;if((x+1)%4==0) return x+1;if(x%4==0) return x-1;return x; }inline int dfs(int num,int sg){if(num==0) return f[num][sg]=(sg!=0);if(f[num][sg]!=-1) return f[num][sg];for(int i=1;i<=min(num,K);++i)if(!dfs(num-i,sg^SG(i*p%P+1))) return f[num][sg]=1;return f[num][sg]=0; }int main(){freopen("double.in","r",stdin);freopen("double.out","w",stdout);scanf("%d%d%d",&n,&p,&K);memset(f,-1,sizeof(f));for(int i=1;i<=min(n,K);++i)if(!dfs(n-i,SG(i*p%P+1))) return printf("%d\n",i),0;puts("-1");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/JCNL666/p/10917914.html

總結(jié)

以上是生活随笔為你收集整理的【题解】大床Nim (2019,5.23)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。