o(T)的dp做法,为啥最后一个点超时
查看原帖
o(T)的dp做法,为啥最后一个点超时
723319
zjj2890986416楼主2023/3/25 16:06
m, s, T = map(int, input().split())
tt = min(m // 10, T)
d = s - 60 * tt
t0 = m // 10
if d <= 0:
    print('Yes')
    print((s - 1) // 60 + 1)
else:
    dp = [[0 for _ in range(10)] for _ in range(T - m // 10 + 1)]
    for i in range(1, T - m // 10 + 1):
        for j in range(10):
            t = (9 - j) // 4 + 1
            if i - t >= 1 and 4 * t - 10 + j >= 0:
                dp[i][j] = max(dp[i - t - 1][j] + 17 * (t + 1), dp[i - t - 1][4 * t - 10 + j] + 60)
            else:
                dp[i][j] = dp[i - 1][j] + 17
    for i in range(1, T - t0 + 1):
        if dp[i][m % 10] >= d:
            print('Yes')
            print(t0 + i)
            break
    else:
        print('No')
        if t0 <= T:
            print(dp[T - t0][m % 10] + s - d)
        else:
            print(60 * T)
2023/3/25 16:06
加载中...