acmicpc.net 10164(DP), 2568(LIS, DP), 11054(LIS, DP)

https://www.acmicpc.net/problem/10164

굳이 설명이 필요없음.

# -*- encoding: cp949 -*-
n,m,k=map(int,raw_input().split())
dp = [[0 for j in xrange(m)] for i in xrange(n)]
dp[0][0] = 1
if k==0:
    k=n*m

row = (k-1)/m
col = (k-1)%m
#print row,col


for i in xrange(n):
    dp[i][0] = 1
for i in xrange(n):
    dp[i][col] = 1

for i in xrange(m):
    dp[0][i] = 1
for i in xrange(m):
    dp[row][i] = 1

for i in xrange(1,row+1):
    for j in xrange(1,col+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

for i in xrange(col+1,m):
    dp[row][i] = dp[row][col]
for i in xrange(row+1,n):
    dp[i][col] = dp[row][col]

for i in xrange(row+1,n):
    for j in xrange(col+1,m):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

#for i in xrange(n):
#    for j in xrange(m):
#        print dp[i][j],
#    print

print dp[n-1][m-1]

https://www.acmicpc.net/problem/2568

LIS의 목록을 구하는 문제. nlogn의 시간복잡도로 LIS를 구하는 코드를 찾아보면 C++

로 stl의 lower_bound를 주로 써서 구현하는데 파이썬의 bisect_left로 대체 가능하다.

# -*- encoding: cp949 -*-
from bisect import bisect_left
def lis(line):
    dp = [0 for i in xrange(100002)]
    fr = [0 for i in xrange(500003)]
    size = 0
    for i in xrange(n):
        h = bisect_left(dp[:size],line[i])
        if h==size: size += 1
        dp[h] = line[i]
        fr[dp[h]] = dp[h-1] if h else 0
    
    i=dp[size-1]
    lis_list = []
    while i:
        lis_list.insert(0,i)
        i = fr[i]
    return lis_list

n=input()
line = sorted([map(int,raw_input().split()) for i in xrange(n)],key=lambda x:x[0])
s_line = map(lambda x:x[1],line)
line = dict(map(lambda x:[x[1],x[0]], line))
for l in lis(s_line):
    del line[l]
print len(line)
for k,v in sorted(line.iteritems(),key=lambda x:x[1]):
    print v

https://www.acmicpc.net/problem/11054

1. 

for(i=0; i<n; i++)

{

  0~i까지의 lis를 구하고

  i~n까지의 lds를 구해서

}

두개의 길이의 합 -1을 해주면 된다.

ex) 1 2 3 5 2 1같은경우.

i==3일때

lis = 1 2 3 5.

lds = 5 2 1이므로 합쳐보면 1 2 3 5 5 2 1이 된다. 근데 중간의 5가 중복되므로 -1을 해주면 답이다.

아래 코드는 lis가 정확하게 나오지는 않지만 lis의 길이는 정확하게 나오는 lis함수 코드다.

lis를 구하는건 두가지가 있는데

1. 숫자가 중복되지 않고, lis의 전체목록을 구하는 경우. nlogn으로 해결 가능

2. 숫자가 중복되고 lis의 전체목록을 구하는 경우. O(n^2)이 필요한듯 싶다. 근데 숫자가 중복되고 lis의 길이만 구하는거면 nlogn으로도 해결 가능하다. 아래 코드처럼.

# -*- encoding: cp949 -*-
from bisect import bisect_left
def lis(line):
    dp = [0 for i in xrange(1002)]
    size = 0
    for i in xrange(len(line)):
        h = bisect_left(dp[:size],line[i])
        if h==size: size += 1
        dp[h] = line[i]
    return size
 
n=input()
line = map(int,raw_input().split())
 
_max = 0
for i in xrange(n):
    l = lis(line[:i+1])
    d = lis(line[i:][::-1])[::-1]
    _max = max(_max, l+d-1)
print _max