C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Ural 1087 The Time to Take Stones 解题报告

Posted on 2011-11-01 14:24 C小加 阅读(1408) 评论(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;
}

 

Feedback

# re: Ural 1087 The Time to Take Stones 解题报告  回复  更多评论   

2011-11-03 21:49 by 浅笑
傻。。。。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理