跳转至

多多传送门

1

多多在玩一个游戏，人物初始位于$x=0$位置，共有$n+1$张卡片可以使用，分别是：

  • n张传送卡（数值为整数，可正可负）： $$ [a_1,a_2,\cdots,a_n] $$
    • 效果是：$x\to x+a_i$
  • 以及一张翻转卡。
    • 效果是：$x\to -x$

n张传送卡片可以按照任意顺序使用，翻转卡可以在任何时候使用。

  • 问：游戏结束时，多多最远能走多远？

  • 样例输入

    4
1 -2 3 -4

  • 样例输出

    10

第一题比较简单，只需要把数组中的正数和负数收集起来相减就行了：

def solution():
    n = int(input())
    l = map(int, input().split())
    s = 0
    for x in l:
        if x>0:
            s += x
        else:
            s -= x
    return s
# print(solution())

2

和第一题同样的题设。

但是这次n张传送卡片只能按照1-n的顺序使用，翻转卡依旧可以在任何时候使用。

  • 问：在游戏过程中，最远的一次能到哪里？

  • 样例输入

    4
1 1 -1 1

  • 样例输出

    3

动态规划

我们可以使用动态规划解决这个问题，三维dp数组dp[i][j][k]：

  • 第一个维度表示使用了第i张传送卡之后所在的最远位置
  • 第二个维度用来区分是否在这个位置使用了反转卡
  • 第三个维度用来记录最大（正）值、最小（负）值

代码如下：

def solution():
    n = int(input())
    l = list(map(int, input().split()))
    dp = [[[0] * 2 for _ in range(2)] for _ in range(n+1)]

    for i in range(n):
        val = l[i]

        # 不用反转卡
        dp[i+1][0][0] = dp[i][0][0] + val
        dp[i+1][0][1] = dp[i][0][1] + val

        # 使用反转卡
        dp[i+1][1][1] = max(
            -dp[i][0][0] + val,
            -dp[i][0][1] + val,
            dp[i][1][0] + val,
            dp[i][1][1] + val,
        )
        dp[i+1][1][0] = min(
            -dp[i][0][0] + val,
            -dp[i][0][1] + val,
            dp[i][1][0] + val,
            dp[i][1][1] + val,
        )
    res = 0
    for i in range(n+1):
        for j in range(2):
            for k in range(2):
                res = max(res, abs(dp[i][j][k]))
    return res
print(solution())

前缀和

  1. 维护一个前缀和数组pos[i]，表示不反转时前 i 步之后的位置
  2. 遍历 0 到 n：
    • i=0表示一开始就反转（x=0 --> x=0），也就是不反转
    • i=1~n 表示在第 i 次传送后反转
  3. 每种情况再模拟从反转点继续往后传送，记录所有位置的 |x| 取最大
def solution():
    n = int(input())
    a = list(map(int, input().split()))
    # 前缀和
    pos = [0] * (n+1)
    for i in range(n):
        pos[i+1] = pos[i] + a[i]
    max_dist = 0
    # 模拟反转点
    for rev_point in range(n+1):
        curr = -pos[rev_point]
        # 继续求和，在过程中不断寻找最大值
        for i in range(rev_point, n):
            curr += a[i]
            if abs(curr) > max_dist:
                max_dist = abs(curr)
    return max_dist
最后更新: 2025-04-07 18:17:49
创建日期: 2024-12-27 23:17:42

评论