UVA10404

由题意可知，这题和巴什博弈没什么关系了

相似题目：AtCoder Beginner Contest 278 F - Shiritori

预备知识：DP，博弈论的必胜态和必败态

问题的关键是确定$f_n$是必胜态还是必败态?

而必胜态由必败态转移而来

如果当前$i-a_j$这个位置是必败态，那么$i$这个位置就是必胜态
由于$m$比较多，我们考虑用DP来转移状态
其中0代表必败态，1代表必胜态
转移方程 $f_i=1 $ $(0≤i-a_j,f_{i-a_{j}}=0)$
单个数据的时间复杂度 $O(mn)$

//  AC one more times

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N = 1e6+10;

int a[11],n,m,f[N];

int main()

{

    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);

    // 特殊输入 请注释上方，如__int128等

    int TC = 1;

    while(cin>>n)

    {

    	cin>>m;

    	for(int i=1;i<=m;i++)	cin>>a[i];

    	for(int i=1;i<=n;i++)	f[i]=0;

    	// 0 代表必输态

    	// 1 代表必胜态

    	for(int i=1;i<=n;i++)

    		for(int j=1;j<=m;j++)

    			if(i>=a[j]&&f[i-a[j]]==0)

    				f[i]=1;

    	if(f[n])

    		cout<<"Stan wins"<<endl;

    	else cout<<"Ollie wins"<<endl;

    }

    return 0;

}

巴特西

UVA10404

最新文章

热门文章