Skip to content

Latest commit

 

History

History
100 lines (81 loc) · 3.67 KB

0045.虚拟棋盘对战.md

File metadata and controls

100 lines (81 loc) · 3.67 KB

汽水瓶换饮料

题目链接

C++

Java

/**
 * 思路：动态规划
 * 用F[l][r]表示先选的人能拿到的最高分
 * 用S[l][r]来表示后选的人能拿到的最高分
 * 对于先选者，有两种选法
 *     若先选者选A[0],则对于后面的1, ... ,n-1 数组，他就变成了后选者，此时能拿到的分为A[0]+S[1][n-1]
 *     若先选者选A[n-1],则对于前面的数组0，...，n-2,同样变为后选者，此时能拿到得分为A[n-1]+S[0][n-2];
 *     所以 F[0][n-1] = max(A[0]+S[1][n - 1],A[n - 1]+S[0][n - 2])
 * 对于后选者，他能能到的最高分是受先选者控制的，即他只能选到先选者留给他的最小值，将其转化为数学形式就是
 * S[l][r] = min(F[l + 1][r], F[l][r - 1])，因为先选者很聪明，肯定会把最低的分数留给他
*/

import java.util.Scanner;

public class MaxScore {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        System.out.println(findMaxScore(array, n));
        scanner.close();
    }
    public static int findMaxScore(int[] A, int n) {
        int[][] F = new int [n][n];
        int[][] S = new int [n][n];
        for (int r = 0; r < n; r++) {
            F[r][r] = A[r];
            S[r][r] = 0;
            for (int l = r - 1; l >= 0; l--) {
                F[l][r] = Math.max(A[l] + S[l + 1][r], A[r] + S[l][r - 1]);
                S[l][r] = Math.min(F[l + 1][r], F[l][r - 1]);
            }
        }
        return Math.max(F[0][n - 1], S[0][n - 1]);
    }
}

Python

# 第四题
# 之前做过石子游戏问题，跟这道题基本相同，动态规划思路如下：
"""
我们可以创建一个二维数组 dp，其中 dp[i][j] 表示玩家在面对剩余的格子区间 [i, j] 时，能够获得的最大分数差值（玩家A的得分减去玩家B的得分）
状态方程分两种情况：

如果玩家选择左端点（格子 i），那么他会获得格子 i 上的分数 nums[i]，然后将剩余的格子区间变成 [i+1, j]，交给对手。所以，得分差值为 nums[i] - dp[i+1][j]。
如果玩家选择右端点（格子 j），那么他会获得格子 j 上的分数 nums[j]，然后将剩余的格子区间变成 [i, j-1]，交给对手。所以，得分差值为 nums[j] - dp[i][j-1]。
玩家会选择让得分差值最大化的那一种情况。所以 dp[i][j] 取两种情况中的较大值，这样玩家就能采用最优策略来最大化自己的得分。

我们在外层定义的循环用于遍历选取的子序列的长度，循环内部的I和J用于指代两端
"""

def stoneGame(nums):
    n = len(nums)
    
    # 创建一个二维数组dp，dp[i][j]表示从第i个石头到第j个石头之间的最大得分
    dp = [[0] * n for _ in range(n)]
    
    # 初始化dp数组，单个石头的得分就是它自己的分数
    for i in range(n):
        dp[i][i] = nums[i]
    
    # 动态规划计算dp数组
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
    
    # 最终dp[0][n-1]表示玩家A和玩家B的得分差值
    # 计算两名玩家的最终得分
    total_score_a = (sum(nums) + dp[0][n - 1]) // 2
    total_score_b = sum(nums) - total_score_a
    
    # 输出得分较高的玩家的得分
    return max(total_score_a, total_score_b)

n = int(input())
s = input().split(" ")
nums = [int(x) for x in s]
print(stoneGame(nums=nums))

Go

JS

C