跳转至

多多传送门

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

评论