题目描述
两个人玩取球的游戏。
一共有 N 个球，每人轮流取球，每次可取集合 {n1,n2,n3} 中的任何一个数目。
如果无法继续取球，则游戏结束。
此时，持有奇数个球的一方获胜。
如果两人都是奇数，则为平局。
假设双方都采用最聪明的取法，第一个取球的人一定能赢吗？
试编程解决这个问题。
输入格式
第一行 3 个正整数 n1,n2,n3，空格分开，表示每次可取的数目。
第二行 5 个正整数 x1,x2,…,x5，空格分开，表示 5 局的初始球数。
输出格式
一行 5 个字符，空格分开。分别表示每局先取球的人能否获胜。能获胜则输出 +，次之，如有办法逼平对手，输出 0，无论如何都会输，则输出 -。
数据范围
0<n1,n2,n3<100,
0<xi<1000
样例
输入样例1：
1 2 3
1 2 3 4 5
输出样例1：
+ 0 + 0 -
输入样例2：
1 4 5
10 11 12 13 15
输出样例2：
0 - 0 + +
输入样例3：
2 3 5
7 8 9 10 11
输出样例3：
+ 0 0 0 0
算法1
暴力递归 过六个数据
C++ 代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n[3]; //每次可以拿走的球数
int x[5]; //x[i]:第i+1局的开始球数
int nums[2]; //num[i]:第i+1个取球的人已经有的球
char ans[3]={'+','0','-'}; //答案结果
//第k+1个人先手取球时，剩余球数rest，已有球数nums[]，返回第k+1个人的结果;
int f(int n[],int rest,int nums[],int k){
if(n[0]>rest){ //不能取球，游戏结束
if(nums[k]%2){
if(nums[(k+1)%2]%2) //俩个人手上的球都为奇数，平局
return 1;
else //第k+1个人手上的球为奇数，第(k+1)%2+1个人球为偶数，则第k+1个人赢
return 0;
}else{
if(nums[(k+1)%2]%2) //第k+1个人手上球为偶数，第(k+1)%2+1个人球为奇数，则第k+1个人输
return 2;
else //两人手上球都为偶数，还是平局。
return 1;
}
}
int MIN=3; //第k个人绝顶聪明，必然选择最可能获胜的决策
for(int i=0;i<3;i++){
if(rest>=n[i]){ //保证rest不会小于0，即rest>=0;
nums[k]+=n[i]; //更新nums[]数组
MIN=min(MIN,2-f(n,rest-n[i],nums,(k+1)%2)); //如果第k+1个人先手，那么下次就是第(k+1)%2+1个人先手，结果互斥
nums[k]-=n[i]; //恢复现场
}else{
break;
}
}
return MIN;
}
int main(){
for(int i=0;i<3;i++)
cin>>n[i];
for(int i=0;i<5;i++)
cin>>x[i];
sort(n,n+3); //从小到大排序
for(int i=0;i<5;i++){ //5局判断
nums[0]=0,nums[1]=0; //每局开始初始化nums[]数组
cout<<ans[f(n,x[i],nums,0)]<<" ";
}
return 0;
}
算法2
记忆化搜索 过八个数据
C++ 代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
int n[3]; //每次可以拿走的球数
int x[5]; //x[i]:第i+1局的开始球数
int nums[2]; //num[i]:第i+1个取球的人已经有的球
//int dp[1010][110][110][2]; 内存太大
unordered_map<string,int> mp; //采用哈希表进行记忆化搜索
char ans[3]={'+','0','-'}; //答案结果
string numToString(int num){
return to_string(num);
}
//第k+1个人先手取球时，剩余球数rest，已有球数nums[]，返回第k+1个人的结果;
int f(int n[],int rest,int nums[],int k){
if(n[0]>rest){ //不能取球，游戏结束
if(nums[k]%2){
if(nums[(k+1)%2]%2) //俩个人手上的球都为奇数，平局
return 1;
else //第k+1个人手上的球为奇数，第(k+1)%2+1个人球为偶数，则第k+1个人赢
return 0;
}else{
if(nums[(k+1)%2]%2) //第k+1个人手上球为偶数，第(k+1)%2+1个人球为奇数，则第k+1个人输
return 2;
else //两人手上球都为偶数，还是平局。
return 1;
}
}
int MIN=3; //第k个人绝顶聪明，必然选择最可能获胜的决策
for(int i=0;i<3;i++){
if(rest>=n[i]){ //保证rest不会小于0，即rest>=0;
nums[k]+=n[i]; //更新nums[]数组
string s=numToString(rest-n[i])+'_'+numToString(nums[0])+'_'+numToString(nums[1])+'_'+numToString((k+1)%2);
if(mp.find(s)!=mp.end())
MIN=min(MIN,2-mp[s]);
else{
mp[s]=f(n,rest-n[i],nums,(k+1)%2);
MIN=min(MIN,2-mp[s]); //如果第k+1个人先手，那么下次就是第(k+1)%2+1个人先手，结果互斥
}
nums[k]-=n[i]; //恢复现场
}else{
break;
}
}
return MIN;
}
int main(){
for(int i=0;i<3;i++)
cin>>n[i];
for(int i=0;i<5;i++)
cin>>x[i];
sort(n,n+3); //从小到大排序
for(int i=0;i<5;i++){ //5局判断
nums[0]=0,nums[1]=0; //每局开始初始化nums[]数组
cout<<ans[f(n,x[i],nums,0)]<<" ";
}
return 0;
}
算法3
动态规划（失败的动态规划）
加入了多于的判断，导致只过了5个数据
C++ 代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<memory.h>
using namespace std;
int n[3]; //每次可以拿走的球数
int x[5]; //x[i]:第i+1局的开始球数
//int nums[2]; //num[i]:第i+1个取球的人已经有的球
//int dp[1010][110][110][2]; 内存太大
//unordered_map<string,int> mp; //采用哈希表进行记忆化搜索
//dp[i][j][k]: 此时剩余球数为i,第一个人拿到的球数为j,且轮到第k+1个人先手取球时的最好结果
int dp[1010][1010][2]; //动态规划
char ans[4]={'+','0','-','*'}; //答案结果
bool check(int f,int s,int n[],int k){ //轮到第k+1个人拿球，但还没拿
if(f<0||s<0)
return false;
if(f==0&&s>0)
return false;
if((k==0)&&f==s&&f==0)
return true;
bool flag=0;
for(int i=0;i<3;i++){
if(k==0){
if(check(f,s-n[i],n,(k+1)%2)){
flag=1;
break;
}
}else{
if(check(f-n[i],s,n,(k+1)%2)){
flag=1;
break;
}
}
}
return flag;
}
int main(){
for(int i=0;i<3;i++)
cin>>n[i];
for(int i=0;i<5;i++)
cin>>x[i];
sort(n,n+3); //从小到大排序
for(int kk=0;kk<5;kk++){ //5局判断
for(int i=0;i<=x[kk];i++)
for(int j=0;j<=x[kk];j++)
for(int k=0;k<2;k++)
dp[i][j][k]=3;
for(int i=0;i<n[0];i++){ //剩余球数小于可以拿到的最小球数，游戏结束。
for(int j=n[0];j<=x[kk]-i;j++){ //第1个人已经拿到的球数
if(check(j,x[kk]-j-i,n,0))
dp[i][j][0]=(j%2==(x[kk]-j-i)%2)?1:(j%2==1?0:2); //轮到第1个人拿球
if(check(j,x[kk]-j-i,n,1))
dp[i][j][1]=(j%2==(x[kk]-j-i)%2)?1:(j%2==1?2:0); //轮到第2个人拿球
}
}
for(int i=n[0];i<=x[kk];i++){ //剩余球数 i
for(int j=0;j<=x[kk]-i;j++){ //第1个人已经拿到的球数 j
for(int k=0;k<2;k++){ //第k+1个人先手取球时
int MIN=3; //dp[i][j][k]=3代表不可能事件
for(int p=0;p<3;p++){
if(n[p]<=i){ //保证i不越界
if(k==0){//cout<<i<<j<<endl;
if(j+n[p]<=x[kk]&&dp[i-n[p]][j+n[p]][(k+1)%2]!=3) //保证j不越界
MIN=min(MIN,2-dp[i-n[p]][j+n[p]][(k+1)%2]);
}
else{
if(dp[i-n[p]][j][(k+1)%2]!=3)
MIN=min(MIN,2-dp[i-n[p]][j][(k+1)%2]);
}
}else{
break;
}
}
dp[i][j][k]=MIN;
}
}
}
cout<<ans[dp[x[kk]][0][0]]<<" ";
}
return 0;
}
算法4
成功的动态规划 AC
C++ 代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n[3]; //每次可以拿走的球数
int x[5]; //x[i]:第i+1局的开始球数
//dp[i][j][k]: 此时剩余球数为i,第一个人拿到的球数为j,且轮到第k+1个人先手取球时的最好结果
int dp[1010][1010][2]; //动态规划
char ans[4]={'+','0','-','*'}; //答案结果
int main(){
for(int i=0;i<3;i++)
cin>>n[i];
for(int i=0;i<5;i++)
cin>>x[i];
sort(n,n+3); //从小到大排序
for(int kk=0;kk<5;kk++){ //5局判断
for(int i=0;i<=x[kk];i++) //初始化dp数组
for(int j=0;j<=x[kk];j++)
for(int k=0;k<2;k++)
dp[i][j][k]=3;
for(int i=0;i<n[0];i++){ //剩余球数小于可以拿到的最小球数，游戏结束。
for(int j=0;j<=x[kk]-i;j++){ //第1个人已经拿到的球数
dp[i][j][0]=(j%2==(x[kk]-j-i)%2)?1:(j%2==1?0:2); //轮到第1个人拿球
dp[i][j][1]=(j%2==(x[kk]-j-i)%2)?1:(j%2==1?2:0); //轮到第2个人拿球
}
}
for(int i=n[0];i<=x[kk];i++){ //剩余球数 i
for(int j=0;j<=x[kk]-i;j++){ //第1个人已经拿到的球数 j
for(int k=0;k<2;k++){ //第k+1个人先手取球时
int MIN=3; //dp[i][j][k]=3代表不可能事件
for(int p=0;p<3;p++){
if(n[p]<=i){ //保证i不越界
if(k==0){
if(j+n[p]<=x[kk]&&dp[i-n[p]][j+n[p]][(k+1)%2]!=3) //保证j不越界
MIN=min(MIN,2-dp[i-n[p]][j+n[p]][(k+1)%2]);
}
else{
if(dp[i-n[p]][j][(k+1)%2]!=3)
MIN=min(MIN,2-dp[i-n[p]][j][(k+1)%2]);
}
}else{
break;
}
}
dp[i][j][k]=MIN;
}
}
}
cout<<ans[dp[x[kk]][0][0]]<<" ";
}
return 0;
}
算法5
优化后的动态规划(不考虑空间优化) AC
C++ 代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n[3]; //每次可以拿走的球数
int x[5]; //x[i]:第i+1局的开始球数
//dp[i][j][k]: 此时剩余球数为i,第一个人拿到的球数为j,且轮到第k+1个人先手取球时的最好结果
int dp[1010][1010][2]; //动态规划
char ans[4]={'+','0','-','*'}; //答案结果
int main(){
for(int i=0;i<3;i++)
cin>>n[i];
for(int i=0;i<5;i++)
cin>>x[i];
sort(n,n+3); //从小到大排序
for(int kk=0;kk<5;kk++){ //5局判断
for(int i=0;i<=x[kk];i++) //初始化dp数组
for(int j=0;j<=x[kk];j++)
for(int k=0;k<2;k++)
dp[i][j][k]=3;
for(int i=0;i<n[0];i++){ //剩余球数小于可以拿到的最小球数，游戏结束。
for(int j=0;j<=x[kk]-i;j++){ //第1个人已经拿到的球
dp[i][j][0]=(j%2==(x[kk]-j-i)%2)?1:(j%2==1?0:2); //轮到第1个人拿球
}
}
for(int i=0;i<n[0];i++){ //剩余球数小于可以拿到的最小球数，游戏结束。
for(int j=n[0];j<=x[kk]-i;j++){ //第1个人已经拿到的球数，轮到第二个人时，第一个人至少拿了n[0]个球
dp[i][j][1]=(j%2==(x[kk]-j-i)%2)?1:(j%2==1?2:0); //轮到第2个人拿球
}
}
for(int i=n[0];i<=x[kk];i++){ //剩余球数 i
for(int j=0;j<=x[kk]-i;j++){ //第1个人已经拿到的球数 j
int MIN=3; //dp[i][j][k]=3代表不可能事件
for(int p=0;p<3;p++){
if(n[p]<=i){ //保证i不越界
if(j+n[p]<=x[kk]&&dp[i-n[p]][j+n[p]][1]!=3) //保证j不越界
MIN=min(MIN,2-dp[i-n[p]][j+n[p]][1]);
}else{
break;
}
}
dp[i][j][0]=MIN;
}
for(int j=n[0];j<=x[kk]-i;j++){ //第1个人已经拿到的球数 j，轮到第二个人时，第一个人至少拿了n[0]个球
int MIN=3; //dp[i][j][k]=3代表不可能事件
for(int p=0;p<3;p++){
if(n[p]<=i){ //保证i不越界
if(dp[i-n[p]][j][0]!=3)
MIN=min(MIN,2-dp[i-n[p]][j][0]);
}else{
break;
}
}
dp[i][j][1]=MIN;
}
}
cout<<ans[dp[x[kk]][0][0]]<<" ";
}
return 0;
}
..........
%%%