主页 / 问题 / 1600925
Accepted
user27630724
Asked:2024-11-27 00:38:39 +0800 CST2024-11-27 00:38:39 +0800 CST

DP 任务。我不明白出了什么问题

  • 772

通过问题E-蚱蜢和青蛙的解决方案 满分：100 时间限制：2秒 实时限制：5秒 内存限制：256M 问题E：蚱蜢和青蛙 问题条件（pdf）

蚱蜢沿着位于同一条线上且彼此距离相等的柱子跳跃。这些列的序列号为 1 到 N。一开始，蚱蜢坐在编号为 1 的柱子上。他可以向前跳跃 1 到 K 柱的距离，从当前的柱子开始计算。

有些帖子上有青蛙吃蚱蜢（蚱蜢不应该落在这些帖子上！）。确定 Grasshopper 可以通过多少种方式安全到达编号为 N 的列。请记住，Grasshopper 无法向后跳。输入格式 输入字符串包含自然数 N 和 K，以空格分隔。保证1≤N，K≤32。第二行包含青蛙的数量 L (0≤L≤N−2)。第三行包含L个自然数：青蛙所坐的列数（其中没有数字为1和N的列）。

Примеры
Входные данные
6 4
2
2 4
Выходные данные
3

我不明白出了什么问题，并非所有测试都通过

n, k = map(int, input().split())
l = int(input())
s_l = list(map(int, input().split()))
dp = [1] * n
dp_1 = []
for i in range(l):
    dp[s_l[i] - 1] = 0
dp_1 = []
dp_1.append(dp[0])
print(dp)
for i in range(1,n):
    if dp[i] == 0:
        pass
    else:
        if i < k:
            dp_1.append(sum(dp_1[:i]))
        else:
            dp_1.append(sum(dp_1[i - k:i]))
print(dp_1[-1])
python-3.x

1 个回答

  1. Best Answer

    您dp1不添加带有青蛙的列，这意味着按范围进行的计算将会混乱 -i - k它将捕获比必要的更早的列

    if dp[i] == 0:
    dp_1.append(0)

    PS 实际上，为什么需要 dp1 呢？

    n, k = map(int, input().split())
l = int(input())
s_l = list(map(int, input().split()))
dp = [1] * n
for i in range(l):
    dp[s_l[i] - 1] = 0
for i in range(1,n):
    if dp[i]:
        if i < k:
            dp[i] = sum(dp[:i])
        else:
            dp[i] = sum(dp[i - k:i])
print(dp[-1])

    下一步，如果需要对大N（对于N=32就可以了）进行优化，就是放弃每次求和，并通过累加（累积）和的差值来找到范围的总和。

    为此，我们将获得的 dp[] 值汇总到一个附加列表 cumsum[] 中

    cumsum[i] = cumsum[i-1] + dp[i]

    并且总和sum(dp[i - k:i])等于差cumsum[i-1] -cumsum[i-k-1]。

    但更重要的是，在这种情况下不需要单独的列表。我们只需将结果值相加并减去区间左端的值（我就写在这里，需要更精确地检查索引）

     dp[i] = partsum
 partsum  += dp[i]
 if i >= k:
    partsum -= dp[i-k-1]
    • 4

相关问题