[白俊1965]箱に入れる🧠✨
5845 ワード
🥚質問する
https://www.acmicpc.net/problem/1965
🥚入力/出力
🍳コード#コード#
import sys
import bisect
input = sys.stdin.readline
n = int(input())
arr = [0] + list(map(int, input().split()))
# LIS = O(NlogN)
# dp[i] = 길이가 i인 증가하는 부분 수열의 마지막 숫자의 최소값
def LIS():
dp = [0]
for i in range(1, n+1):
if arr[i] > dp[-1]:
dp.append(arr[i])
else:
idx = bisect.bisect_left(dp, arr[i]) # 이분탐색으로 들어갈 자리 찾기
dp[idx] = arr[i]
return len(dp) - 1
ans = LIS()
print(ans)
🧂アイデア
DP, LIS
import sys
import bisect
input = sys.stdin.readline
n = int(input())
arr = [0] + list(map(int, input().split()))
# LIS = O(NlogN)
# dp[i] = 길이가 i인 증가하는 부분 수열의 마지막 숫자의 최소값
def LIS():
dp = [0]
for i in range(1, n+1):
if arr[i] > dp[-1]:
dp.append(arr[i])
else:
idx = bisect.bisect_left(dp, arr[i]) # 이분탐색으로 들어갈 자리 찾기
dp[idx] = arr[i]
return len(dp) - 1
ans = LIS()
print(ans)🧂アイデア
DP, LIS
以前は何度か関連問題を解いたが,O(Nlogn)時間の複雑さを持つアルゴリズムを実現する上では誤りがあるようだ.今日解いたとき突然...これじゃないの?考えて修正しました.
格納ボックスサイズのリストarrを巡回する場合、arr[i]がdpの最後の値より大きい場合、dpにarr[i]を追加します.
arr[i]がdpの最後の値より小さい場合、arr[i]に含まれる可能性のあるインデックスを二分的に検索し、dp[idx]=arr[i]に更新します.
このN個の入力に対して二分検索を実行するので、時間の複雑さはO(Nlogn)です!
注2:最長の2進数列
注3：最も長い減少部分数列
注4:最大増分4
Reference
この問題について([白俊1965]箱に入れる🧠✨), 我々は、より多くの情報をここで見つけました https://velog.io/@eastgloss0330/백준-1965-상자넣기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol