재밌었던 DP 모음 - 1

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

 

그림을 축을 기준으로 뒤집는 문제.

일단 n이 홀수면 뭘 해도 거울에 반사된 상태로 보이기때문에 불가능

d도인 선으로 그림을 뒤집으면 2*d 만큼 각도를 조정할 수 있다.

근데 세계가 뒤바껴있는 상태에서는 -2*d 만큼 작용한다.

홀수 인덱스에선 2*d, 짝수 인덱스에선 -2*d를 적용하여 냅색하고 역추적해주자

 

---

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

 

 

문자열이 주어지고 문자 u 뒤에 문자 v가 오지 않도록 하는 서브시퀀스의 개수를 구하는 문제

 

dp(i) = i번 인덱스의 문자를 끄트머리에 사용한 문자열의 개수

f(c) = 문자 c를 가장 끄트머리에 사용한 문자열의 개수

 

dp(i) = sum(f(c))+1 조건을 만족하는 c

f(s[i]) = dp(i)

로 쉽게 전이가 된다.

 

어차피 맨 끝 문자열만 관리하면 서브시퀀스가 유니크함을 보장할 수 있기 때문이다.

 

---

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

 

 

겹치는 구간끼리 적어도 하나는 집합에 넣어줘야 하는데, 그 집합의 개수를 세는 문제

 

(s, e) 기준으로 정렬한 후

f(i) = i번 열차를 확정하였을 때 경우의 수

만약 i번 열차에 부착한다면 더 볼 것 없이 f(i+1)을 호출하면 된다.

i번 열차에 부착하지 않는다면,

i번 열차와 겹치는 열차 j(s_j < e_i)는 반드시 부착되어야한다.

따라서 겹치는 열차를 건너뛰고 그 다음을 호출해주면 되겠다.

f(i) = f(i+1) + f(j+1)로 전이가 가능하고,

 

열차 j+1는 우리가 초기에 s, e 기준으로 정렬하였기 때문에 이분탐색으로 구해줄 수 있다.

 

i번 열차를 미부착했을때 이전 상황을 고려하지 않아도 되는 이유는

i번 열차가 부착되어야하는 경우였다면 어차피 i번 열차를 뛰어넘었을 것이기 때문

 

---

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

 

 swoon: 문제요약
 swoon: N개의 배달을 마쳐야하는데
 swoon: 배달은 (x, y)로 물품을 쏴줘야한다
 swoon: 나는 수직선상에서 y=t or x=t와 같은 직선위로만돌아다닐수있고
 swoon: 배달위치랑 같은 x좌표 or y좌표 위에만 있으면 된다
 swoon: 배달완료하는최소시간
 swoon: 물품주어진순서대로 배달해야함

 

그냥 평범한 경찰차dp처럼 보일수있으나 N <= 20000이다.

근데 난 O(N^2)으로 풀었다.

그래서 다른 풀이는 모름

 

---

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

 

a와 b로 1, 2, ... k를 나눠가지는 경우의 수를 구하는 문제

 

쉽게 식을 세워보면

f(i, j, k) = 빨강 i통, 파랑 j통을 모두 사용하여, 크기 k인 그림을 그리는 경우의 수

f(i, j, k) -> f(i+k+1, j, k+1), f(i, j+k+1, k+1)

다음과 같이 두 개의 전이가 가능하다.

 

i+j = (k+1)k/2를 만족해야하므로

j가 없어도 i, k만으로 유니크한 j가 특정된다.

 

f(i, k) = 빨강 i통, 파랑 (k+1)k/2-i통을 모두 사용하여 크기 k인 그림을 그리는 경우의 수

f(i, k) -> f(i+k+1, k+1), f(i, k+1)

 

쿼리를 처리해야하는데

쿼리마다 ans = sum(sum{0 <= i <= a}(f(i, k))) <= 이걸 구해야댐

k번 시행은 ㄱㅊ으니까 넘어가고

sum{0 <= i <= a}(f(i, k)) 이거만 빨리 구하면 노상관이다.

걍 누적합 하면 될거같은데

k(k+1)/2 <= i+b 조건을 만족해야한다.

그럼 식은 sum{k(k+1)/2-b <= i <= a}(f(i, k)) 으로 바뀌고

누적합으로 구해주면 O(AK + QK)로 풀 수 있다.