글 읽기 - 어떤 반례가 있을까요?

hsw0194 2년 전 0

질문게시판하고 예제 통과하는데 어떤반례까 잇을까요?

dp[i][w][0] : i초에 w만큼 움직이고 1번째 나무에 잇을때 최댓값

dp[i][w][1] : i초에 w만큼 움직이고 2번째 나무에 있을때 최댓값

from sys import stdin

T, W = map(int, stdin.readline().split())


def sol():
    dp = [[[0 for _ in range(31)] for _ in range(2)] for _ in range(1001)]

    first_tree = [False for _ in range(1001)]
    second_tree = [False for _ in range(1001)]

    for t in range(T):
        pos = int(stdin.readline())

        if pos == 1:
            first_tree[t + 1] = True
        else:
            second_tree[t + 1] = True

    if first_tree[1]:
        dp[1][0][0] = 1
    else:
        dp[1][1][1] = 1

    for i in range(2, T + 1):
        for k in range(W + 1):
            if k == 0:
                dp[i][0][0] = dp[i - 1][0][0]
                dp[i][1][0] = dp[i - 1][1][0]
            else:
                dp[i][0][k] = max(dp[i - 1][0][k], dp[i - 1][1][k - 1])
                dp[i][1][k] = max(dp[i - 1][0][k - 1], dp[i - 1][1][k])

            if first_tree[i]:
                dp[i][0][k] += 1
            else:
                dp[i][1][k] += 1
    return max(max(dp[T]))


print(sol())

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 반례가 있을까요?

hsw0194 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말