DP (Small)

• DP (Large)의 쉬운 버전. 풀이는 링크 참고. 코드도 동일하다.
• 제한이 작아서, O(n^2)에 LIS를 구해도 풀리기는 하다.

"""Solution code for "BOJ 31501. DP (Small)".

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

Tags: [lis]
"""

import sys
from teflib import seqtask


def main():
    _N, Q = [int(x) for x in sys.stdin.readline().split()]
    D = [int(x) for x in sys.stdin.readline().split()]

    len_by_last = seqtask.longest_inc_subseq_length_by_last_elem(D)
    len_by_first = seqtask.longest_inc_subseq_length_by_first_elem(D)

    for _ in range(Q):
        A = int(sys.stdin.readline()) - 1
        print(len_by_last[A] + len_by_first[A] - 1)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.seqtask.longest_inc_subseq_length_by_last_elem
  • teflib.seqtask.longest_inc_subseq_length_by_first_elem