首页 > 试题广场 > 双人数字游戏
[编程题]双人数字游戏
  • 热度指数:256 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
游戏规则如下
- 在棋盘上有N个数字(A1~AN)从左到右排列成一行
- A,B两个玩家轮流进行游戏,第一回合A玩家行动,第二回合B玩家行动,依次行动直到游戏结束
- 每回合玩家可以选择拿走棋盘上最左边或者最右边的一个数字,其余的都不能拿
- 拿走的数字依次从左到右排列在自己面前
- 棋盘上所有数字被拿走后游戏结束
- 最优策略的说明:在任意局面下,玩家如果取左边的数字或者取右边的数字,最终最优得分都一样,那么只能取左边的数字

当所有数字都被拿走后,A,B两个玩家面前都各有一个数列。
假设A玩家面前数字从左到右为 X1,X2,X3...XM,则他的最终得分Sa计算方式如下(B玩家的得分计算Sb也类似,不赘述):
Sa = abs(X1-0) + abs(X2-X1) + abs(X3-X2) + ... + abs(XM - X(M-1))


请计算在以上的规则下,如果两个玩家都想拿到尽量多的分数,用最优策略进行游戏,计算两个人的最终得分。


输入描述:
第一行一个数字 N, 一半的测试用例 (0 < N <= 50),一半的测试用例 (0 < N <= 1000)
第二行N个数字 Ai ( 0 <= Ai <= 50)


输出描述:
用空格隔开的两个整数Sa和Sb
示例1

输入

4
1 2 3 4

输出

7 4
第二次做动态规划题, 所以想了很久, 后效性很难消除. 尝试多次, 终于AC. 以下为我的解法:
二维动态规划,金字塔dp[][]
dp[0][i]记录只剩两个数字Xi和Xi+1的所有情况:   LL    L    Xi    Xi+1    R    RR    
L表示数组a中X1左边的数字, LL表示L左边的数字, R, RR同理.(超出界限取0)
对于先手玩家和后手玩家, 现在有4种情况: 
    先手已经取了LL, 后手取了L:(LL    L    Xi    Xi+1), 则A选择与LL差的绝对值较大的X, B只能取剩余的X
    先手已经取了RR, 后手取了R:(Xi    Xi+1    R    RR), 则A选择与RR差的绝对值较大的X, B只能取剩余的X
    先手已经取了L, 后手取了R:(L    Xi    Xi+1    R), 则A选择与L差的绝对值较大的X, B只能取剩余的X
    先手已经取了R, 后手取了L:(L    Xi    Xi+1    R), 则A选择与R差的绝对值较大的X, B只能取剩余的X
    记录每种情况先手玩家和后手玩家的分值

dp[1][i]记录剩余三个数字X1, X2, X3的情况: LL    L    Xi    Xi+1    Xi+2    R    RR
对于先手玩家和后手玩家, 现在有4种情况: 
    先手已经取了LL, 后手取了L :     
        先手取Xi则将问题转化为(dp[0][i+1])的(LL    L    Xi+1    Xi+2)情况 
            则先手得分为上述情况的后手得分+本次选数得分, 
            后手得分为上述情况的先手得分
        先手取Xi+2则将问题转化为(dp[0][i])的(L    Xi    Xi+1    R)情况, 同理
    先手已经取了RR, 后手取了R:
        先手取Xi则将问题转化为(dp[0][i+1])的(L    Xi+1    Xi+2    R)情况, 同理
        先手取Xi+2则将问题转化为(dp[0][i])的(Xi    Xi+1    R    RR)情况, 同理
    先手已经取了L, 后手取了R, 
        先手取Xi则将问题转化为(dp[0][i+1])的(L    Xi+1    Xi+2    R)情况, 同理
        先手取Xi+2则将问题转化为(dp[0][i])的(Xi    Xi+1    R    RR) 同理
    先手已经取了R, 后手取了L, 
        先手取Xi则将问题转化为(dp[0][i+1])的(LL    L    Xi+1    Xi+2)情况, 同理
        先手取Xi+2则将问题转化为(dp[0][i])的(L    Xi    Xi+1    R)情况, 同理
    记录每种情况先手玩家和后手玩家的分值
以此类推, 直到dp[n-1][0]
半个2维数组还是很大, 可以使用一维数组, 进一步优化空间.
using System;
class Program
{
    const int nMax = 1000;
    static int n;
    static int[] a = new int[nMax + 4];
    static Node[][] dp = new Node[nMax - 1][];
    static void Main(string[] args)
    {
        n = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        for (int i = 2; i < n + 2; i++)
        {
            a[i] = int.Parse(str[i - 2]);
        }
        a[0] = a[1] = a[n + 2] = a[n + 3] = 0;
        dp[0] = new Node[n - 1];//最下面一层(只剩两个数的所有情况)
        for (int i = 0; i < n - 1; i++)
        {
            dp[0][i] = new Node();
        }
        int aIndex;
        int lqian, lhou, llqian, llhou, rqian, rhou, rrqian, rrhou;
        //计算最下面一层(每两个数计算一次)
        for (int i = 0; i < n - 1; i++)
        {

            aIndex = i + 2;
            lqian = Math.Abs(a[aIndex - 1] - a[aIndex]);
            lhou = Math.Abs(a[aIndex - 1] - a[aIndex + 1]);
            llqian = Math.Abs(a[aIndex - 2] - a[aIndex]);
            llhou = Math.Abs(a[aIndex - 2] - a[aIndex + 1]);
            rqian = Math.Abs(a[aIndex + 2] - a[aIndex]);
            rhou = Math.Abs(a[aIndex + 2] - a[aIndex + 1]);
            rrqian = Math.Abs(a[aIndex + 3] - a[aIndex]);
            rrhou = Math.Abs(a[aIndex + 3] - a[aIndex + 1]);
            //ll
            if (llqian >= llhou)
            {//如果先手选前一个
                dp[0][i].ll[0] = llqian; //先手选前一个
                dp[0][i].ll[1] = lhou; //后手只能选后一个
            }
            else
            {//如果先选后一个
                dp[0][i].ll[0] = llhou; //先手选后一个
                dp[0][i].ll[1] = lqian; //后手只能选前一个
            }
            //rr
            if (rrqian >= rrhou)
            {
                dp[0][i].rr[0] = rrqian;
                dp[0][i].rr[1] = rhou;
            }
            else
            {
                dp[0][i].rr[0] = rrhou;
                dp[0][i].rr[1] = rqian;
            }
            //lr
            if (lqian >= lhou)
            {
                dp[0][i].lr[0] = lqian;
                dp[0][i].lr[1] = rhou;
            }
            else
            {
                dp[0][i].lr[0] = lhou;
                dp[0][i].lr[1] = rqian;
            }
            //rl
            if (rqian >= rhou)
            {
                dp[0][i].rl[0] = rqian;
                dp[0][i].rl[1] = lhou;
            }
            else
            {
                dp[0][i].rl[0] = rhou;
                dp[0][i].rl[1] = lqian;
            }
        }
        int t1, t2;
        int qian, hou, l, r, ll, rr;
        //主循环
        for (int j = 1; j < n - 1; j++)
        {//计算第j层(只剩j+2个数的所有情况)
            dp[j] = new Node[n - 1 - j];
            for (int i = 0; i < n - 1 - j; i++)
            {
                dp[j][i] = new Node();
            }
            for (int i = 0; i < n - 1 - j; i++)
            {
                qian = i + 2;
                hou = qian + 1 + j;
                l = i + 1;
                ll = i;
                r = hou + 1;
                rr = hou + 2;
                //ll
                t1 = Math.Abs(a[ll] - a[qian]) + dp[j - 1][i + 1].ll[1]; //先手取前
                t2 = Math.Abs(a[ll] - a[hou]) + dp[j - 1][i].lr[1]; //先手取后
                if (t1 >= t2)
                {
                    dp[j][i].ll[0] = t1;
                    dp[j][i].ll[1] = dp[j - 1][i + 1].ll[0];
                }
                else
                {
                    dp[j][i].ll[0] = t2;
                    dp[j][i].ll[1] = dp[j - 1][i].lr[0];
                }
                //rr
                t1 = Math.Abs(a[rr] - a[qian]) + dp[j - 1][i + 1].rl[1];
                t2 = Math.Abs(a[rr] - a[hou]) + dp[j - 1][i].rr[1];
                if (t1 >= t2)
                {
                    dp[j][i].rr[0] = t1;
                    dp[j][i].rr[1] = dp[j - 1][i + 1].rl[0];
                }
                else
                {
                    dp[j][i].rr[0] = t2;
                    dp[j][i].rr[1] = dp[j - 1][i].rr[0];
                }
                //lr
                t1 = Math.Abs(a[l] - a[qian]) + dp[j - 1][i + 1].rl[1];
                t2 = Math.Abs(a[l] - a[hou]) + dp[j - 1][i].rr[1];
                if (t1 >= t2)
                {
                    dp[j][i].lr[0] = t1;
                    dp[j][i].lr[1] = dp[j - 1][i + 1].rl[0];
                }
                else
                {
                    dp[j][i].lr[0] = t2;
                    dp[j][i].lr[1] = dp[j - 1][i].rr[0];
                }
                //rl
                t1 = Math.Abs(a[r] - a[qian]) + dp[j - 1][i + 1].ll[1];
                t2 = Math.Abs(a[r] - a[hou]) + dp[j - 1][i].lr[1];
                if (t1 >= t2)
                {
                    dp[j][i].rl[0] = t1;
                    dp[j][i].rl[1] = dp[j - 1][i + 1].ll[0];
                }
                else
                {
                    dp[j][i].rl[0] = t2;
                    dp[j][i].rl[1] = dp[j - 1][i].lr[0];
                }
            }
        }
        Console.WriteLine(dp[n - 2][0].ll[0] + " " + dp[n - 2][0].ll[1]);
    }
}
class Node
{
    public int[] ll = new int[2];//上次取了左边两个
    public int[] rr = new int[2];//上次取了右边两个
    public int[] lr = new int[2];//上次先手取了左边,后手取了右边
    public int[] rl = new int[2];//上次先手取了右边,后手取了左边
}


编辑于 2021-04-05 01:28:37 回复(0)
原本以为是每次都选择abs较大的那个,提交后发现正确率为8%。
#include<iostream>
#include<math.h>
using namespace std;
 
int main()
{
    int n,a[1000],sub1 = 0,sub2 = 0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int l=0,r=n-1,temp1=0,temp2=0;
    while(l<=r)
    {
        if(a[l]==a[r])
        {
            sub1 += abs(a[l] - temp1);
            temp1 = a[l];
            l++;
        }
        else if(abs(a[l] - temp1) > abs(a[r] - temp1))
        {
            sub1 += abs(a[l] - temp1);
            temp1 = a[l];
            l++;
        }
        else{
            sub1 += abs(a[r] - temp1);
            temp1 = a[r];
            r--;
        }
        if(l>r) break;
        if(a[l]==a[r])
        {
            sub2 += abs(a[l] - temp2);
            temp2 = a[l];
            l++;
        }
        else if(abs(a[l] - temp2) > abs(a[r] - temp2))
        {
            sub2 += abs(a[l] - temp2);
            temp2 = a[l];
            l++;
        }
        else{
            sub2 += abs(a[r] - temp2);
            temp2 = a[r];
            r--;
        }
    }
    cout<<sub1<<" "<<sub2;
}
读题感觉自己想错了,重写代码,但不知为何堆栈溢出,应该是递归过多吧,内存占用太大了。
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int N;
int Arr[1000];
vector<int> sa, sb;
int Max_Sa, Max_Sb;
//求绝对值和
int Sum(vector<int> vct)
{
	int sum = 0;
	int temp = 0;
	for (int i = 0; i < vct.size(); i++)
	{
		sum += abs(temp - vct[i]);
		temp = vct[i];
	}
	return sum;
}

void Update_Sa(vector<int> vct)
{
	sa.clear();
	for (int i = 0; i < vct.size(); i++)
		sa.push_back(vct[i]);
}

void Update_Sb(vector<int> vct)
{
	sb.clear();
	for (int i = 0; i < vct.size(); i++)
		sb.push_back(vct[i]);
}

//计算Sa的选择
void Sa_Choise(int begin, int end, vector<int> vct)
{
	if (begin > end)
	{
		int suma = Sum(vct);
		if (suma > Max_Sa)
		{
			Max_Sa = suma;
			Update_Sa(vct);
		}
		return;
	}
	vct.push_back(Arr[begin]);//Sa选择第一个
	begin++;
	if (begin > end)
	{
		int suma = Sum(vct);
		if (suma > Max_Sa)
		{
			Max_Sa = suma;
			Update_Sa(vct);
		}
		return;
	}
	Sa_Choise(++begin, end, vct);//如果Sb选择了第一个
	Sa_Choise(--begin, --end, vct);//如果Sb选择了最后一个
	begin--;//还原
	vct.pop_back();
	vct.push_back(Arr[++end]);//Sa选择最后一个
	end--;
	if (begin > end)
	{
		int suma = Sum(vct);
		if (suma > Max_Sa)
		{
			Max_Sa = suma;
			Update_Sa(vct);
		}
		return;
	}
	Sa_Choise(++begin, end, vct);//如果Sb选择了第一个
	Sa_Choise(--begin, --end, vct);//如果Sb选择了最后一个
}

//计算Sb的选择
void Sb_Choise(int begin, int end, vector<int> vct)
{
	if (begin > end)
	{
		int sumb = Sum(vct);
		if (sumb > Max_Sb)
		{
			Max_Sb = sumb;
			Update_Sb(vct);
		}
		return;
	}
	vct.push_back(Arr[begin]);//Sb选择第一个
	begin++;
	if (begin > end)
	{
		int sumb = Sum(vct);
		if (sumb > Max_Sb)
		{
			Max_Sb = sumb;
			Update_Sb(vct);
		}
		return;
	}
	Sb_Choise(++begin, end, vct);//如果Sa选择了第一个
	Sb_Choise(--begin, --end, vct);//如果Sa选择了最后一个
	begin--;//还原
	vct.pop_back();
	vct.push_back(Arr[++end]);//Sb选择最后一个
	end--;
	if (begin > end)
	{
		int sumb = Sum(vct);
		if (sumb >= Max_Sb)
		{
			Max_Sb = sumb;
			Update_Sb(vct);
		}
		return;
	}
	Sb_Choise(++begin, end, vct);//如果Sa选择了第一个
	Sb_Choise(--begin, --end, vct);//如果Sa选择了最后一个
}

void NumberGame()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> Arr[i];
	int begin = 0, end = N - 1;
	int i = 0;
	while (begin <= end)
	{
		Max_Sa = 0, Max_Sb = 0;
		Sa_Choise(begin, end, sa);
		while (sa.size() > i + 1)
			sa.pop_back();
		if (sa[i] == Arr[begin]) begin++;
		else if (sa[i] == Arr[end]) end--;
		if (begin > end)
			break;
		Sb_Choise(begin, end, sb);
		while (sb.size() > i + 1)
			sb.pop_back();
		if (sb[i] == Arr[begin]) begin++;
		else if (sb[i] == Arr[end]) end--;
		i++;
	}
}

int main()
{
	NumberGame();
	cout << Max_Sa << " " << Max_Sb;
	return 0;
}
但根据第一次结果的测试数据中,case(10,100,1,1)的结果应为(100,19)而我的依旧是(19,199),它应该是a选(1,100),b选(10,1),但由于a的可能性里包括(10,100)、(10,1)、(1、100)、(1、10)对应的分数分别为100、19、100、10,所以,我的程序中a先选择的是10而不是1,case通过不了,把判定方式由>改为>=后,发现最终分数为(100,10)也不是case的答案,a方案为(1,100)而b选择为(1,10),因为当a选了1以后,b可能选择(10,100)、(10,1)、(1,100)、(1,10)对应结果为100、19、100、10,故而由于判定方式选后面的方案,b第一次选择为1,而a紧跟选100后,b只能选10,分数为(100,10)。这里有题目中的最优策略未增加,使用最优策略后,感觉a在第一次选择时,相比于(1、100)更倾向于(10、100),也达不到case的分数。。。。
发表于 2021-03-07 15:56:04 回复(0)
还没写,不知道思路有没有问题。
二维动态规划,从只有四个数的情况开始推导整个数组的情况,dp(i~j) = max(chose_left(dp(i+1~j)), choose_right(dp(i~j-1))),要存当前状态的先后手分数和每人最先取的数。最外面一层特殊处理abs(x1-0)。
发表于 2020-08-16 20:58:52 回复(0)
//测试数据看不懂了。。。。
 
#include<iostream>
#include<vector>
using namespace std;
int getnum(vector<int> &nums,int &a){
      int tmp=0;
    if(abs(nums[0]-a)>=abs(nums[nums.size()-1]-a))
    {
        
        tmp=abs(nums[0]-a);
        a=nums[0];
        nums.erase(nums.begin(),nums.begin()+1);
    }else{
        tmp=abs(nums[nums.size()-1]-a);
        a=nums[nums.size()-1];
        nums.pop_back();
    }
    return tmp;
}
int main(){
    int n;
    cin>>n;
    vector<int> nums(n,0);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    int sa=0,sb=0;
    int a=0,b=0;
    for(int i=0;i<n;i++){
        if(i%2==0)
        {
            sa+=getnum(nums,a);
        }else{
   
            sb+=getnum(nums,b);
        }
    }
     cout<<sa<<" "<<sb<<endl;
    return 0;
}

编辑于 2020-08-02 16:41:21 回复(0)