双人数字游戏-世界杯葡萄牙阵容-2034年世界杯_足球中国世界杯预选赛

首页

题库

面试

求职

学习

竞赛

搜索面经/职位/试题/公司

搜索

我要招人

去企业版

首页

试题广场

双人数字游戏

[编程题]双人数字游戏

热度指数：532

时间限制：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

输入

1 2 3 4

输出

7 4

马上挑战

算法知识视频讲解

提交运行

算法知识视频讲解

添加笔记

求解答(18)

邀请回答

纠错

提交结果有问题?

10个回答

0篇题解

添加回答

不如诗啊

第二次做动态规划题, 所以想了很久, 后效性很难消除. 尝试多次, 终于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

紙の蝉

#include

using namespace std;

const int maxn = 1e3+10;

int a[maxn];

int dp[3][3][maxn][maxn][2];

int calc(int x, int y, int apre=2,int bpre = 2){

int value = 0;

if(apre == 2){

return 0;

}

if(apre==0 && bpre ==0){

value = a[x-2];

}else if(apre==0 && bpre ==1){

value = a[x-1];

}else if(apre==1 && bpre ==0){

value = a[y+1];

}else if(apre==1 && bpre ==1){

value = a[y+2];

}

return value;

}

int dfs(int apre, int bpre, int x, int y, int stat, int &pre_nextans){

if(x>y){

return 0;

}

if(dp[apre][bpre][x][y][0]!=-1){

pre_nextans = dp[apre][bpre][x][y][0];

return dp[apre][bpre][x][y][1];

}

int nextans = 0;

int best_nextans = 0;

int ans = -1;

if(stat == 0){

int value = calc(x,y,apre,bpre);

// 取左

int res = dfs(0,bpre,x+1,y,!stat,nextans) + abs(value-a[x]);

if(res>ans){

ans = res;

best_nextans = nextans;

}

// 取右

res = dfs(1,bpre,x,y-1,!stat,nextans) + abs(value-a[y]);

if(res>ans){

ans = res;

best_nextans = nextans;

}

}else{

int value = calc(x,y,bpre,apre);

// 取左

int res = dfs(apre,0,x+1,y,!stat,nextans) + abs(value-a[x]);

if(res>ans){

ans = res;

best_nextans = nextans;

}

// 取右

res = dfs(apre,1,x,y-1,!stat,nextans) + abs(value-a[y]);

if(res>ans){

ans = res;

best_nextans = nextans;

}

// 便于计算返回的是下一个的最大值

dp[apre][bpre][x][y][0] = ans;

dp[apre][bpre][x][y][1] = best_nextans;

pre_nextans = ans;

return best_nextans;

}

int main() {

int n;

while (cin >> n) { // 注意 while 处理多个 case

memset(dp,-1,sizeof(dp));

for(int i=0;i

cin>>a[i];

}

int nextvalue = 0;

dfs(2,2,0,n-1,0,nextvalue);

cout<

}

} dp 的维度开的有点高了。记忆化搜索的dp写法比较好理解一点，dp数组的几个维度分别是第一二维度为两方数列上一次取得是左边还是右边，初始化2表示还没取(这里偷懒了，用多一点空间)。第三四维度表示剩下的需要取的左右坐标。第五维度用来多记录一个值，因为这里的dp是间断的，用来计算的是甲乙都取了一次后的值，即下下次dp得到的结果。递归里面多了个引用也是偷懒了，间断保存下下次的值。

发表于 2025-05-11 01:32:56

米饭盛半

// dfs + 记忆化搜索

#include

using namespace std;

vector>>> memo1;

vector>>> memo2;

pair dfs(vector& nums, int left, int right, int prev1, int prev2, int term) {

if (left > right) {

return {0, 0};

}

int key = prev1 * 51 + prev2;

if (term == 0) {

auto iter = memo1[left][right].find(key);

if (iter != memo1[left][right].end())

return iter->second;

auto [SAL, SBL] = dfs(nums, left + 1, right, nums[left], prev2, 1);

SAL += abs(prev1 - nums[left]);

auto [SAR, SBR] = dfs(nums, left, right - 1, nums[right], prev2, 1);

SAR += abs(prev1 - nums[right]);

if (SAL >= SAR)

return memo1[left][right][key] = {SAL, SBL};

else

return memo1[left][right][key] = {SAR, SBR};

}

else {

auto iter = memo2[left][right].find(key);

if (iter != memo2[left][right].end())

return iter->second;

auto [SAL, SBL] = dfs(nums, left + 1, right, prev1, nums[left], 0);

SBL += abs(prev2 - nums[left]);

auto [SAR, SBR] = dfs(nums, left, right - 1, prev1, nums[right], 0);

SBR += abs(prev2 - nums[right]);

if (SBL >= SBR)

return memo2[left][right][key] = {SAL, SBL};

else

return memo2[left][right][key] = {SAR, SBR};

}

int main() {

int n;

cin >> n;

vector nums(n);

int num;

for (int i = 0; i < n; i++) {

cin >> nums[i];

}

memo1 = vector>>> (n, vector>> (n));

memo2 = vector>>> (n, vector>> (n));

auto [result1, result2] = dfs(nums, 0, n - 1, 0, 0, 0);

cout << result1 << " " << result2 << endl;

}

发表于 2024-08-16 14:48:13

Python

冰块十字架

这是一个不符合题目要求的答案，但理论上这个答案可以完成任务（搜索路径指数爆炸），完成度为10/50。思路是通过函数递归，直接遍历所有情况返回最大值。 import sys

lines = []

try:

while True: # 获取所有输入

line = sys.stdin.readline().strip()

if line == "":

break

lines.append(line.split())

except:

pass

N = int(lines[0][0])

l = []

for i in lines[1]:

l.append(int(i))

del lines

# 搜索路径本质是一个二叉树，那么从树枝向上传播，即可得到最优解

def search(Sa, Sb, l, A, B, term):

# Sa,Sb为A，B当前的总分

# l是剩余的数字

# A,B是A，B上次取的数字

if len(l) > 0: # 如果l还没取完

if term: # 轮到A

SaR, SbR = search(Sa + abs(l[0] - A), Sb, l[1:], l[0], B, False)

SaL, SbL = search(Sa + abs(l[-1] - A), Sb, l[:-1], l[-1], B, False)

if SaR < SaL: # A的回合，A会选择对自己有利的

return SaL, SbL

else:

return SaR, SbR

else: # 轮到B

SaR, SbR = search(Sa, Sb + abs(l[0] - B), l[1:], A, l[0], True)

SaL, SbL = search(Sa, Sb + abs(l[-1] - B), l[:-1], A, l[-1], True)

if SbR < SbL: # B的回合，B会选择对自己有利的

return SaL, SbL

else:

return SaR, SbR

# l被取完后，统计总分

return Sa, Sb

SaM, SbM = search(0, 0, l, 0, 0, True)

print(SaM, SbM)

发表于 2023-04-21 00:01:19

牛客143762745号

%8的是没有考虑对手也会用最优解。可以看下minmax算法和alpha beta pruning

发表于 2022-09-18 14:17:29

永远的小白虾

通过率8% 就是一个贪心算法的解法。直接比较abs（x[i]-x[i-1]）值的大小，陷入了局部最优。 #include

#include

using namespace std;

int main(){

int n;

cin>>n;

vector nums(n,0);

for(int i=0;i

{

cin>>nums[i];

}

vector sa;

vector sb;

int left=0;

int right=n-1;

sa.emplace_back(0);

sb.emplace_back(0);

for(int i=0;i

{

if(i%2==0)//sa

{

if(abs(nums[left]-sa[sa.size()-1])>=abs(nums[right]-sa[sa.size()-1]))

{

sa.emplace_back(nums[left++]);

}else

{

sa.emplace_back(nums[right--]);

}

else{//sb

if(abs(nums[left]-sb[sb.size()-1])>=abs(nums[right]-sb[sb.size()-1]))

{

sb.emplace_back(nums[left++]);

}else

{

sb.emplace_back(nums[right--]);

}

int saCount=0;//计算sa的值

for(int i=1;i

{

saCount+=abs(sa[i]-sa[i-1]);

}

int sbCount=0;//计算sb的值

for(int i=1;i

{

sbCount+=abs(sb[i]-sb[i-1]);

}

cout<

return 0;

}

发表于 2021-08-08 22:44:05

牛客719032233号

这题看着最简单简答，结果是最难的......

发表于 2021-08-06 20:43:29

牛客140844664号

原本以为是每次都选择abs较大的那个，提交后发现正确率为8%。 #include

#include

using namespace std;

int main()

{

int n,a[1000],sub1 = 0,sub2 = 0;

cin>>n;

for(int i=0;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<

} 读题感觉自己想错了，重写代码，但不知为何堆栈溢出，应该是递归过多吧，内存占用太大了。 #include

#include

using namespace std;

int N;

int Arr[1000];

vector sa, sb;

int Max_Sa, Max_Sb;

//求绝对值和

int Sum(vector 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 vct)

{

sa.clear();

for (int i = 0; i < vct.size(); i++)

sa.push_back(vct[i]);

}

void Update_Sb(vector 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 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 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

Raven1996

还没写，不知道思路有没有问题。二维动态规划，从只有四个数的情况开始推导整个数组的情况，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

小朋友608

//测试数据看不懂了。。。。

#include

using namespace std;

int getnum(vector &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 nums(n,0);

for(int i=0;i

cin>>nums[i];

}

int sa=0,sb=0;

int a=0,b=0;

for(int i=0;i

if(i%2==0)

{

sa+=getnum(nums,a);

}else{

sb+=getnum(nums,b);

}

cout<

return 0;

}

编辑于 2020-08-02 16:41:21

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

游戏研发工程师

网易游戏雷火

上传者：小小

难度：

10条回答

40收藏

6976浏览