[백준] 2240번: 자두나무

https://www.acmicpc.net/problem/2240

Initial brute-force implementation

[Sep 6th 23] I still can't implement the brute-force way. Tbc

n, moves = map(int,input().split())
lst = list(int(input()) for _ in range(n))
dp=[0 for _ in range(moves+1)]
for i in range(len(lst)):
    temp_index=i
    temp_moves=moves
    temp_value = lst[i]
    count=0
    while(temp_moves>=0 and temp_index<n):
        if(lst[temp_index]!=temp_value):
            temp_moves-=1
            temp_value = lst[temp_index]
        
        temp_index +=1
        count+=1
    dp[lst[i]] = max(dp[lst[i]], count)
print(max(dp))

how to fix this fuckkkkkkkkkkkkkkkkkkkkkkkkkkkk

i tried

n, moves = map(int,input().split())
lst = list(int(input()) for _ in range(n))
dp=[0 for _ in range(moves+1)]
for i in range(len(lst)):
    temp_index=i
    temp_moves=moves
    temp_value = lst[i]
    count=0
    while(temp_moves>0 and temp_index<n):
        if(lst[temp_index]!=temp_value):
            temp_moves-=1
            temp_value = lst[temp_index]
            temp_index +=1
            count+=1
        else:
            if temp_moves>0 and temp_index<n:
                temp_index +=1
                count+=1
            else:
                break

    dp[lst[i]] = max(dp[lst[i]], count)
print(max(dp))

Finally I tried

n, moves = map(int,input().split())
lst = list(int(input()) for _ in range(n))
dp=[[0 for _ in range(moves+1)] for _ in range (n+1)]
for i in range(n+1):
    if lst[i]==1:
        dp[i][0] = dp[i-1][0]+1
    else:
        dp[i][0] = dp[i-1][0]
    for j in range(1,moves+1):
        if lst[i]==1 and j%2==0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+1
        elif lst[i]==2 and j%2==1:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])
print(max(dp[n]))

but when I was looking at model ans, I thought dp[i-1][0] will surely cause an error because when i=0, i-1 will result in a negative value.

So what the answer did was to append 0 first to the list like

Solution

moves and Trees

We alway start from Tree 1, something that I missed out while reading the question. Anyway, so we are gonna move from stationary (j=0) to the given allowed number of moves (j=j).

First, when we move from Tree 1 to 2, j is 1 (odd) and we are at Tree 2. Then from 2 to 1, j is 2 (even) and we are back at Tree 1. This pattern is same for up to any value of j like 7 or 1 million.

So for a given allowed number of moves (j), we can assume that

• when j is odd (j%2==1), we are at Tree 2
• when j is even (j%2==0), we are at Tree 1

catching plums

Now coincidentally, what if we encounter a plum falling right as we have moved?

• i.e. lst[i]==2 and j%2==1

That means we can catch that plum since we are at Tree 2.

Likewise,

• lst[i]==1 and j%2==0

We can catch that plum at Tree 1.

Else, we can't catch that plum.

DP

Let's take [2, 1, 1, 2, 2, 1, 1] for example.

For each second, we are going to calculate how many plums we can catch when we move from j=0 to j=j and formulate a table.

Our dp[i][j] is the max number of plums collected up to i seconds for given number of j moves taken.

In terms of states, we cannot go back from j=2 to j=1 just because we have used up all available moves and we wanna move more to get more plums cuz we have reached the max moves allowed. So our dp formula would be only allowed j-1 (previous tree position) and j (current tree position) at previous second (i-1)

Explanation tbc cuz I don't 100% get it

import sys

# 자두가 떨어지는 시간 T와 이동할 수 있는 횟수 W
t, w = map(int, sys.stdin.readline().rstrip().split(" "))

# 자두가 떨어지는 나무의 번호 저장
arr = [0]
for _ in range(t):
    arr.append(int(sys.stdin.readline()))

# 2차원 DP 테이블 초기화
dp = [[0] * (w+1) for _ in range(t+1)]

for i in range(t+1):

    # 1번 나무에서 한 번도 움직이지 않는 경우

    # 1번 나무에서 자두가 떨어진다면
    if (arr[i] == 1):
        dp[i][0] = dp[i-1][0] + 1

    # 2번 나무에서 자두가 떨어진다면
    else:
        dp[i][0] = dp[i-1][0]

    # 1번 이상 움직이는 경우에 대해 탐색
    for j in range(1, w+1):

        # i초에 2번 나무에서 자두가 떨어지고, 현재 2번 나무에 위치해있다면
        if (arr[i] == 2 and j % 2 == 1):
            # 이전 위치로부터 움직여서 받아 먹을 것인지, 현재 위치에서 받아 먹을 것인지를 비교
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1

        # i초에 1번 나무에서 자두가 떨어지고, 현재 1번 나무에 위치해있다면
        elif (arr[i] == 1 and j % 2 == 0):
            # 이전 위치로부터 움직여서 받아 먹을 것인지, 현재 위치에서 받아 먹을 것인지를 비교
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1

        # i초에 자두가 떨어지는 나무와 현재 나무의 위치가 다르다면
        else:
            # 움직여서 못 먹는 경우와 움직이지 않아서 못 먹는 경우를 비교
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])

# DP 테이블의 마지막 행의 최댓값을 출력
print(max(dp[t]))