首页 > 试题广场 >

排成一条线的纸牌博弈问题

[编程题]排成一条线的纸牌博弈问题

热度指数：5107 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左和最右的纸牌，玩家A和玩家B绝顶聪明。请返回最后的获胜者的分数。

输入描述:

输出包括两行，第一行一个整数n，代表数组arr长度，第二行包含n个整数，第i个代表arr[i]。

输出描述:

输出一个整数，代表最后获胜者的分数。

示例1

输入

4
1 2 100 4

输出

备注:

时间复杂度,空间复杂度

算法知识视频讲解

Java

pein531

这道题仍然可以用暴力递归尝试改动态规划的套路，先给出暴力的递归尝试（会超时）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++) cards[i] = Integer.parseInt(strCards[i]);
        System.out.println(first(cards, 0, cards.length - 1));     // 假设A玩家先，并让他获胜
    }
    
    // 先手函数
    private static int first(int[] cards, int left, int right) {
        if(left == right) return cards[left];      // 剩最后一张牌，拿走
        // 先手利益最大化
        return Math.max(cards[left] + second(cards, left + 1, right), cards[right] + second(cards, left, right - 1));
    }
    
    // 后手函数
    private static int second(int[] cards, int left, int right) {
        if(left == right) return 0;      // 剩最后一张牌，被先手的拿了
        return Math.min(first(cards, left + 1, right), first(cards, left, right - 1));    // 先手留最少的给后手
    }
}

然后根据递归的依赖关系改出动规版本：(1)有两个递归函数，就有两张动态规划表；(2)对于区间[left,right]上面的结果，dp[left][right]依赖left+1和right-1，因此left从大往小遍历，right从小往大遍历；(3)left不能大于right，因此动态规划表中left>right的区域无效。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++) cards[i] = Integer.parseInt(strCards[i]);
        // 先手和后手一起动规
        int[][] dpFirst = new int[n][n];
        int[][] dpSecond = new int[n][n];
        for(int right = 0; right < n; right ++){
            for(int left = right; left >= 0; left --){
                if(left == right){
                    // 只剩一张牌，先手的拿
                    dpFirst[left][right] = cards[left];
                    dpSecond[left][right] = 0;
                }else if(left < right){
                    dpFirst[left][right] = Math.max(cards[left] + dpSecond[left + 1][right], cards[right] + dpSecond[left][right - 1]);
                    dpSecond[left][right] = Math.min(dpFirst[left + 1][right], dpFirst[left][right - 1]);
                }
            }
        }
        System.out.println(Math.max(dpFirst[0][n - 1], dpSecond[0][n - 1]));
    }
}

编辑于 2021-11-20 17:16:12 回复(0)

杜jc

//一般的递归法和动态规划方法，左神的书已经讲的比较清楚
//这里主要说一说另一种思路
//设胜者的总分为x,败者的总分为y，且有 x - y = diff; //方程一
//又因为两者的分数和为纸牌的总分，则有 x + y = sum; //方程二
//联立方程式可得 x = (sum + diff)/2;
//因此题目就转化为求两者的总分差diff
//令递推公式f(i,j):在剩余的i~j牌中,A(先拿)的分数减去B(后拿)的分数
//因此 f(i,j)=max(arr[i]-f(i+1,j),arr[j]-f(i,j-1));
//上式中的f(i+1,j)为剩余牌中B的分数减去A的分数,加负号并加上arr[i],
//代表A取最左边牌的情况，arr[j]-f(i,j-1)的含义为取最右的情况

//根据递推公式直接递归的方法
//diff = first - second
int getDiffCore(const int *arr, int i, int j);

int winner_Solution3_Recursive(const int arr[], const int len)
{
	if (arr == NULL || len < 1)
		return 0;

	int sum = 0;
	for (int i = 0; i < len; ++i)
		sum += arr[i];

	int diff = getDiffCore(arr, 0, len - 1);
	if (diff < 0)
		diff = -diff;

	return (sum + diff) / 2;
}

int getDiffCore(const int *arr, int i, int j)
{
	if (i == j)
		return arr[i];

	return std::max(arr[i] - getDiffCore(arr, i + 1, j), arr[j] - getDiffCore(arr, i, j - 1));
}


//===================================
//一般的动态规划
int winner_Solution3(const int arr[], const int len)
{
	if (arr == NULL || len < 1)
		return 0;

	int sum = 0;
	for (int i = 0; i < len; ++i)
		sum += arr[i];

	int **f = make2DArray<int>(len, len);
	for (int j = 0; j < len; ++j)
	{
		f[j][j] = arr[j];
		for (int i = j - 1; i >= 0; --i)
		{
			f[i][j] = std::max(arr[i] - f[i + 1][j], arr[j] - f[i][j - 1]);
		}
	}

	int diff = f[0][len - 1];
	if (diff < 0)
		diff = -diff;

	return (sum + diff) / 2;
}



//================================
//空间压缩后，空间复杂度为O(N)
int winner_Solution3(const int arr[], const int len)
{
	if (arr == NULL || len < 1)
		return 0;

	int sum = 0;
	for (int i = 0; i < len; ++i)
		sum += arr[i];

	int *dp = new int[len];
	for (int i = len - 1; i >= 0; --i)
	{
		dp[i] = arr[i];
		for (int j = i + 1; j < len; ++j)
		{
			dp[j] = std::max(arr[i] - dp[j], arr[j] - dp[j - 1]);
		}
	}

	int diff = dp[len - 1];
	if (diff < 0)
		diff = -diff;

	
	return (sum + diff) / 2;
}

发表于 2019-12-27 12:50:23 回复(2)

AnnaSophia_Robb

#include <bits/stdc++.h>
using namespace std;

int win(vector<int> arr, int n){
    vector<int> f(n,0);
    vector<int> s(n,0);
    for(int j=0; j<n; j++){
        f[j] = arr[j];
        s[j] = 0;
        for(int i=j-1; i>=0; i--){
            int k=j, a=f[i];
            f[i] = max(arr[i]+s[i+1], arr[k--]+s[i]); //在纸上画下就知道
            s[i] = min(f[i+1], a);
        }
    }
    return max(f[0], s[0]);
}
int main(){
    int n; scanf("%d", &n);
    if(n == 0) return 0;
    vector<int> arr(n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    cout << win(arr, n);
    return 0;
}

编辑于 2020-02-10 00:37:44 回复(4)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, s=0;
    cin>>n;
    int a[n], dp[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        dp[i] = a[i];
        s += a[i];
    }
    for(int j=1;j<n;j++)
        for(int i=0;i<n-j;i++)
            dp[i] = max(a[i]-dp[i+1], a[i+j]-dp[i]);
    cout<<(s+abs(dp[0]))/2<<endl;
    return 0;
}

发表于 2020-05-21 09:13:05 回复(0)

牛客242021943号

public

发表于 2022-02-22 16:03:28 回复(0)

也曾是少年

n = int(input())
arr = list(map(int,input().split(' ')))

def win2(arr,n):
    if not arr&nbs***bsp;len(arr)==0:
        return 0 
    f = [[0] * n] * n
    s = [[0] * n] * n
    for j in range(n):
        f[j][j] == arr[j]
        for i in range(j-1,-1,-1):
            f[i][j] = max(arr[i]+s[i+1][j], arr[j] + s[i][j-1])
            s[i][j] = min(f[i+1][j], f[i][j-1])
    return max(f[0][n-1] , s[0][n-1])

ans = win2(arr,n)
print(ans)

# 这题python跑不通嘛？ 是O(N^2)也通不过。

编辑于 2021-06-13 17:38:53 回复(0)

牛客887263087号

#include <iostream>
#include <vector>
using namespace std;

// int firstHand(const vector<int>& v, int L, int R);
// int secondHand(const vector<int>& v, int L, int R);

// int firstHand(const vector<int>& v, int L, int R){
// //base case
// if(L == R)
// return v[L];
// return max(v[L] + secondHand(v, L + 1, R),
// v[R] + secondHand(v, L, R - 1));
// }

// int secondHand(const vector<int>& v, int L, int R){
// //base case
// if(L == R)
// return 0;
// return min(firstHand(v, L + 1, R),
// firstHand(v, L, R - 1));
// }

int winnerGrade(const vector<int>& v){
int n = v.size();
vector<vector<int>> f(n, vector<int>(n, 0));
vector<vector<int>> s(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
f[i][i] = v[i];
}
for(int j = 1; j < n; j++){
for(int i = 0; i + j < n; i++){
int L = i;
int R = i + j;
f[L][R] = max(v[L] + s[L + 1][R], v[R] + s[L][R - 1]);
s[L][R] = min(f[L + 1][R], f[L][R - 1]);
}
}
return max(f[0][n - 1], s[0][n - 1]);
}

int main(void){
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++)
cin >> v[i];
cout << winnerGrade(v) << endl;
return 0;

}

注释的是暴力解法

后面根据暴力解法推出的动态规划是最终解法

本质是生成2个上三角矩阵

发表于 2021-05-25 00:38:17 回复(0)

Java

叫我小du

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[][] dpf = new int[n][n];
        int[][] dps = new int[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = n - 1; i >= 0; i--) {
                if (i > j) {
                    continue;
                } else if (i == j) {
                    dpf[i][j] = arr[i];
                    dps[i][j] = 0;
                } else {
                    dpf[i][j] = Math.max(arr[i] + dps[i + 1][j], arr[j] + dps[i][j - 1]);
                    dps[i][j] = Math.min(dpf[i + 1][j], dpf[i][j - 1]);
                }
            }
        }
        int res = Math.max(dpf[0][n - 1], dps[0][n - 1]);
        System.out.println(res);
    }
}

发表于 2021-04-09 14:05:29 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.print(win(n,arr));
    }
    public static int win(int n,int[] arr){
        if(arr==null||n==0){
            return 0;
        }
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for(int j=0;j<n;j++){
            f[j][j]=arr[j];
            for(int i=j-1;i>=0;i--){
                f[i][j]=Math.max(arr[i]+s[i+1][j],arr[j]+s[i][j-1]);
                s[i][j]=Math.min(f[i+1][j],f[i][j-1]);
            }
        }
        return Math.max(f[0][n-1],s[0][n-1]);
    }
}

发表于 2021-03-29 14:41:28 回复(0)

Hyperlens

#include <iostream>
using namespace std;
#define N 5000
int arr[N];
int f[N][N];
int g[N][N];

int max2(int a,int b)
{
    return (a>b? a:b);
}

int min2(int a,int b)
{
    return (a<b? a:b);
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
    
    for(int i=0;i<n;++i)
    {
        f[i][i]=arr[i];
        g[i][i]=0;
    }
    
    // dp process
    for(int len=1;len<n;++len)
    {
        for(int i=0;i+len<n;++i)
        {
            f[i][i+len]=max2(arr[i]+g[i+1][i+len],arr[i+len]+g[i][i+len-1]);
            g[i][i+len]=min2(f[i+1][i+len],f[i][i+len-1]);
        }
    }
    cout<<max2(f[0][n-1],g[0][n-1])<<endl;
    return 0;
}

发表于 2020-08-09 14:28:25 回复(0)

Java

jahentao

动态规划。

假设函数f(i,j)表示绝顶聪明的玩家，先拿[i,j]区间内的纸牌，获得的最大分数；s(i,j)表示绝顶聪明的玩家，后拿[i,j]区间内的纸牌，获得的最大分数。

时间复杂度O(N²)，空间复杂度O(N²)不超过限制，可以压缩为O(N)。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = a[i];
            s[i][i] = 0;
        }
        for (int d = 1; d < n; d++) {
            for (int i = 0; i < n - d; i++) {
                f[i][i + d] = Math.max(a[i] + s[i + 1][i + d], a[i + d] + s[i][i + d - 1]);
                s[i][i + d] = Math.min(f[i + 1][i + d], f[i][i + d -1]);
            }
        }
        System.out.println(Math.max(f[0][n-1], s[0][n-1]));
    }
}

发表于 2020-05-08 07:40:27 回复(0)

繁星似尘

我写了一个记忆化递归的，个人感觉比较好理解，这里子问题的设计还是比较巧妙的（我在另外的题目看到的）。

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int guess(vector<int> &iterms, int left, int right, vector<vector<int> > &dp){

if(left == right){ /* 只有一个，先手可以拿完 */

dp[left][right] = iterms[left];

}

if(dp[left][right] == -1){

/* 可以拿左边的，也可以拿右边的，取最大值 */

dp[left][right] = max(iterms[left] - guess(iterms,left+1,right,dp),iterms[right] - guess(iterms,left,right-1,dp));

}

return dp[left][right];

}

int stoneGame(vector<int>& iterms) {

if(iterms.size() == 0){

return 0;

}

/* dp代表只考虑序列i,j的情况下，先手比后手多的值 */

vector<vector<int> > dp(iterms.size(),vector<int>(iterms.size(),-1));

guess(iterms,0,iterms.size()-1,dp);

return dp[0][iterms.size()-1];

}

int main(int argc, char const *argv[])

{

int n,num;

cin>>n;

vector<int> v;

int sum = 0;

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

cin>>num;

v.push_back(num);

sum += num;

}

int ret = stoneGame(v);

if(ret < 0){ /* 先手可能会输 */

ret = - ret;

}

sum = (sum - ret) / 2 + ret;

cout<<sum<<endl;

system("pause");

return 0;

}

编辑于 2019-08-05 15:31:55 回复(0)

C/C++

王梦池

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
long* nums;
int main()
{
    int n;
    cin >> n;
    nums = new long[n];
    vector<long> first;
    vector<long> second;
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
        second.push_back(0);
    }
    if (n == 1)
    {
        cout << nums[0];
        return 0;
    }
    long sum_j = nums[0];
    for (int j = 1; j < n; j++)
    {
        sum_j += nums[j];
        long sum_i = sum_j;
        first.clear();
        for (int i = 0; i < n - j; i++)
        {
            first.push_back(max(second[i + 1] + nums[i], second[i] + nums[i+j]));
        }
        second.clear();
        for (int i = 0; i < n - j; i++)
        {
            second.push_back(sum_i - first[i]);
            if (i+j < n - 1)
            {
                sum_i = sum_i - nums[i] + nums[i + j + 1];
            }
        }
    }
    cout << max(first[0], second[0])<<endl;
    return 0;

}

//一开始用两个矩阵分别存固定头尾情况下的先后手最优解，后来内存溢出改成堆栈

发表于 2019-08-05 08:41:01 回复(0)

提交观点

问题信息

动态规划思维递归

上传者：小小

难度：

13条回答 68收藏 8262浏览

通过挑战的用户

查看代码

激进的小菜鸡

2023-03-10 18:23:41
Andy9898

2023-03-08 18:25:58
普信员

2023-02-27 21:16:40
牛客98895...

2023-02-23 21:06:40
One Peach

2023-02-03 16:47:31

排成一条线的纸牌博弈问题

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题