周赛笔记219


三、石子游戏 VII

石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始

有 n 块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,并获得与该行中剩余石头值之 相等的得分。当没有石头可移除时,得分较高者获胜。

鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值

给你一个整数数组 stones ,其中 stones[i] 表示 从左边开始 的第 i 个石头的值,如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值


输入:stones = [5,3,1,4,2]
输出6
解释

  • 爱丽丝移除 2 ,得分 5 + 3 + 1 + 4 = 13 。游戏情况:爱丽丝 = 13 ,鲍勃 = 0 ,石子 = [5,3,1,4]
  • 鲍勃移除 5 ,得分 3 + 1 + 4 = 8 。游戏情况:爱丽丝 = 13 ,鲍勃 = 8 ,石子 = [3,1,4]
  • 爱丽丝移除 3 ,得分 1 + 4 = 5 。游戏情况:爱丽丝 = 18 ,鲍勃 = 8 ,石子 = [1,4]
  • 鲍勃移除 1 ,得分 4 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [4]
  • 爱丽丝移除 4 ,得分 0 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = []
    得分的差值 18 - 12 = 6

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        sum = [0] * (n + 1)
        for i in range(n):
            sum[i + 1] = sum[i] + stones[i]

        def get(l, r):
            return sum[r + 1] - sum[l]

        @cache
        def dp(l, r):
            if l == r:
                return 0
            return max(get(l + 1, r) - dp(l + 1, r), get(l, r - 1) - dp(l, r - 1))

        ans = dp(0, n - 1)
        dp.cache_clear()
        return ans

# copy 

四、堆叠长方体的最大高度

给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。

如果 widthi <= widthjlengthi <= lengthjheighti <= heightj ,你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。

返回 堆叠长方体 cuboids 可以得到的 最大高度

class Solution(object):
    def maxHeight(self, cuboids):
        new_cuboids = []
        for x in cuboids:
            new_cuboids.append(sorted(x))
        cuboids = new_cuboids
        n = len(cuboids)
        cuboids.sort(key=lambda x: x[0]*x[1]*x[2])
        dp = [0] * n
        for i in range(n):
            dp[i] = cuboids[i][2]
            for j in range(i):
                if cuboids[j][1]<=cuboids[i][1] and cuboids[j][2] <= cuboids[i][2] and cuboids[j][0] <= cuboids[i][0]:
                    dp[i]=max(dp[i],dp[j]+cuboids[i][2])
        return max(dp)

# copy
# 像 dp 中最长上升子序列

other

石子游戏:https://leetcode-cn.com/problems/stone-game/


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录