테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Cow Jog ======

===== 풀이 =====
  * 같은 레인에서는 추월이 생기지 않는다는 것은 처음 순위가 그대로 유지된다는 것이고.. 처음 시점에서의 대소관계와 마지막 시점에서의 대소관계가 동일하다는 뜻이다. i번 소의 처음 포지션과 마지막 포지션을 x_i, y_i라고 두면, 같은 레인 안에 있는 소에 대해서는 x_1<x_2<...<x_k 이면 y_1<y_2<...<y_k 가 된다, 즉 x를 인덱스로 생각하면 y가 증가 수열을 이룬다.
  * 따라서 이 문제는 최소 몇개의 증가하는 부분 수열로 전체 수열을 커버할수 있는지를 묻는 문제가 되고, [[ps:가장_긴_증가하는_부분_수열#최소 갯수의 non-increasing_subsequence 로 배열을 커버하기]] 에서 설명한대로 이것은 가장 긴 non-increasing_subsequence의 길이를 찾는 것과 동일한 문제가 된다.
  * non-increasing_subsequence는 [[ps:가장_긴_증가하는_부분_수열]]에서 설명한 대로 O(nlogn)에 계산 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 10651. Cow Jog".

- Problem link: https://www.acmicpc.net/problem/10651
- Solution link: http://www.teferi.net/ps/problems/boj/10651

Tags: [LIS]
"""

import bisect
import sys

MOD = 10_007


def main():
    N, T = [int(x) for x in sys.stdin.readline().split()]
    final_pos = []
    for _ in range(N):
        pos, speed = [int(x) for x in sys.stdin.readline().split()]
        final_pos.append(pos + speed * T)

    # Longest non-increasing sequence.
    arr = []
    for x in final_pos:
        lis_len = bisect.bisect_right(arr, -x)
        if lis_len == len(arr):
            arr.append(-x)
        else:
            arr[lis_len] = -x

    print(len(arr))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}