2565

LIS를 이루는 것을 알아내고 나면 쉽게 풀어낼 수 있다. LIS 기본 문제는 다음을 참고하도록 하자. 2022.01.16 - [프로그래밍/알고리즘] - [BOJ 11053] 가장 긴 증가하는 부분수열 - LIS 예제의 B 전봇대를 보도록 하자. A 전봇대의 B 전봇대의 타겟을 수열로 나타내면, 8 2 9 1 4 6 7 10 이다. 수열이 증가하는 순서라면 엉키지 않는다. 따라서, 최대 증가 부분 수열을 이루는 부분을 제외하고 나머지 전깃줄을 제거하면 답을 구할수 있다. LIS의 길이를 구하고, 전깃줄의 개수에서 빼준다. #include #include #include int LineTargets[501]= { 0 , }; int main() { std::cin.tie(0); std::cout.tie(0..