0

我正在尝试从 Code Jam 的 2021 年资格赛中为Moons 和 Umbrellas提出 DP 解决方案。以下是我的工作递归解决方案，基于他们的分析：

import sys
from functools import lru_cache

sys.setrecursionlimit(5000)

T = int(input())

for case in range(1, T+1):
    X, Y, S = input().split()
    X = int(X)
    Y = int(Y)
    S = tuple(S)

    @lru_cache(maxsize=128)
    def cost(S):
        if len(S) <= 1:
            return 0

        if S[0] == '?':
            return min(cost(('C',) + S[1:]), cost(('J',) + S[1:]))

        if S[0] != '?' and S[1] == '?':
            return min(cost((S[0],) + ('C',) + S[2:]), cost((S[0],) + ('J',) + S[2:]))

        if S[0] == S[1]:
            return cost(S[1:])

        if S[0] == 'C' and S[1] == 'J':
            return X + cost(S[1:])

        if S[0] == 'J' and S[1] == 'C':
            return Y + cost(S[1:])

    print(f'Case #{case}: {cost(S)}')

简而言之，问题是给定一串C's、J's 和?s（例如CCJCJ??JCor JCCC??CJ），问号应替换为Cor J。最小化从C到转换的成本，J反之亦然。这两种类型的转换具有不同的成本。

如何使用自下而上的方法将其转换为 DP 解决方案？

4

1 回答 1

1

此解决方案适用于所有 3 个测试集：

T = int(input())

C, J = 0, 1
INF = float('inf')

for case in range(1, T+1):
    X, Y, S = input().split()
    X = int(X)  # CJ
    Y = int(Y)  # JC

    dp = [[None, None] for _ in range(len(S))]

    for i, c in enumerate(S):
        if i == 0:
            if c == 'C':
                dp[i][C] = 0
                dp[i][J] = INF
            elif c == 'J':
                dp[i][J] = 0
                dp[i][C] = INF
            elif c == '?':
                dp[i][C] = 0
                dp[i][J] = 0
        else:
            if c == 'C':
                dp[i][J] = INF
                if S[i-1] == 'C':
                    dp[i][C] = dp[i-1][C]
                elif S[i-1] == 'J':
                    dp[i][C] = dp[i-1][J] + Y
                elif S[i-1] == '?':
                    dp[i][C] = min(dp[i-1][C], dp[i-1][J] + Y)
            elif c == 'J':
                dp[i][C] = INF
                if S[i-1] == 'C':
                    dp[i][J] = dp[i-1][C] + X
                elif S[i-1] == 'J':
                    dp[i][J] = dp[i-1][J]
                elif S[i-1] == '?':
                    dp[i][J] = min(dp[i-1][J], dp[i-1][C] + X)
            elif c == '?':
                if S[i-1] == 'C':
                    dp[i][C] = dp[i-1][C]
                    dp[i][J] = dp[i-1][C] + X
                elif S[i-1] == 'J':
                    dp[i][C] = dp[i-1][J] + Y
                    dp[i][J] = dp[i-1][J]
                elif S[i-1] == '?':
                    dp[i][C] = min(dp[i-1][C], dp[i-1][J] + Y)
                    dp[i][J] = min(dp[i-1][J], dp[i-1][C] + X)

    print(f'Case #{case}: {min(dp[-1])}')
于 2021-11-01T06:41:43.940 回答