[일반] 에망센 문제가 가장긴 바이토닉수열 확장판임

[익명(39.7)]

밖이라 대충 씀
내용 복구해보면
n개 수열이 있고
s = 1 이면 1 4 1
s = 2 이면 1 4 1 4 1
처럼 위아래 왔다갔다하는 수열 합이 최소가되게만드는 수열 구하는거
골라야하는 수열의갯수는 2s + 1 개

[익명(39.7)]

이해안가면 물어보셈

[0xrgb(0xrgb)]

N개의 수와 S가 주어지고 2s+1의 합이 최소가 되는 바이토닉 수열을 찾는거임?

[0xrgb(0xrgb)]

subsequence임 substring임?

[익명(39.7)]

ㅇㅇ 그런느낌, 점진적자살은 , O(n)풀이 주장중이고 프갤에 걔가 쓴글있음

[익명(39.7)]

시퀸스

[익명(39.7)]

시퀸스가 떨어져있는 수열맞지?

[0xrgb(0xrgb)]

ㅇㅇ

[0xrgb(0xrgb)]

일단 제일 쉬운게 O(NS^2)일거고 생각 좀만 더해보면 줄일 수 있을듯

[익명(39.7)]

여튼 점진이는 그 풀이좀 봐달라는거임

[0xrgb(0xrgb)]

업데이트 할때 새로운 수열이 가장 최소라는 증명이 약한데

[점진적자살(114.70)]

헉\

[점진적자살(114.70)]

그러네 진짜

[점진적자살(114.70)]

보조정리 역도 증명해야하네

[점진적자살(114.70)]

역 성립 안함 ㅅㅂ

[ㅁㅇ(14.36)]

서브스트링 아니였냐? 이어져있었는데

[0xrgb(0xrgb)]

서브스트링이면 너무 쉬움

[0xrgb(0xrgb)]

그냥 쭉 읽으면서 해결하면 됨

[ㅁㅇ(14.36)]

아 시퀀스 마즘ㅋㅋ