結果

問題 No.484 収穫
ユーザー lam6er
提出日時 2025-04-16 00:13:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,298 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 526,140 KB
最終ジャッジ日時 2025-04-16 00:14:47
合計ジャッジ時間 24,341 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 9 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
a = list(map(int, input().split()))
INF = float('inf')

# Using 1-based indices for cells (1 to n)
# dp[l][r][0] is the time when covering [l..r] ending at l
# dp[l][r][1] is the time when covering [l..r] ending at r
dp = [[[INF] * 2 for _ in range(n + 2)] for __ in range(n + 2)]

for i in range(1, n + 1):
    dp[i][i][0] = a[i - 1]
    dp[i][i][1] = a[i - 1]

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        # Calculate dp[l][r][0] (ending at left end l)
        # Option 1: come from [l+1..r] ending at left (l+1)
        option1 = dp[l + 1][r][0] + 1
        # Option 2: come from [l+1..r] ending at right (r)
        option2 = dp[l + 1][r][1] + (r - l)
        dp[l][r][0] = min(option1, option2)
        dp[l][r][0] = max(dp[l][r][0], a[l - 1])  # Ensure we can harvest at l
        
        # Calculate dp[l][r][1] (ending at right end r)
        # Option 1: come from [l..r-1] ending at right (r-1)
        option1 = dp[l][r - 1][1] + 1
        # Option 2: come from [l..r-1] ending at left (l)
        option2 = dp[l][r - 1][0] + (r - l)
        dp[l][r][1] = min(option1, option2)
        dp[l][r][1] = max(dp[l][r][1], a[r - 1])  # Ensure we can harvest at r

answer = min(dp[1][n][0], dp[1][n][1])
print(answer)
0