Posted on 2011-11-01 14:24
C小加 閱讀(1528)
評論(1) 編輯 收藏 引用 所屬分類:
解題報告
博弈+DP。
我的博弈很菜啊，看了討論區才知道該如何博弈，然后就很自然的想到了DP。
先找出石子總數是1的時候先手肯定能贏的狀態，然后找2，直至找到n。每一次狀態的選定都依據之前的狀態。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXM=53;
const int MAXN=10003;
int a[MAXM];
int f[MAXN];
int main()
{
memset(f,0,sizeof(f));
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>a[i];
}
f[0]=1;//初始化，當沒有石子的時候先手必勝
for(int i=1;i<=n;i++)//石子總數從1枚舉到n
{
for(int j=0;j<m;j++)//枚舉取石子的所有可能性
{
if(i>=a[j]&&f[i-a[j]]==0)//如果先手拿了a[j]數量的石子，剩下的石子后手必敗，那么這個狀態下先手必勝
{
f[i]=1;
break;
}
}
}
cout<<2-f[n]<<endl;
return 0;
}