재밌었던 DP 모음 - 2, 심심풀이 문제

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

 

엄청 긴 문자열이 주어졌을 때 서로다른 서브시퀀스의 개수를 구하는 문제

f(c) = 현재 위치까지 봤을 때 문자 c가 가장 마지막으로 오는 유니크한 서브시퀀스의 개수라고 정의하자.

만약 vi가 1이라면

f(c) = sum(f(i))+1임을 바로 알 수 있다.

 

여기에 연산을 한 번 더 적용하면 f(c) = (sum(f(i))+1)*2 - f(c)가 된다.

유니크한 문자열 뒤에 c를 이어붙인 뒤, 한 번 더 이어붙이는 것을 반복하면

f(c) = (sum(f(i))+1)*vi - f(c)*(vi-1) 임을 알 수 있다.

시각적으로 표현해도 쉽게 나옴

 

---

 

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

 

격자에서 텐트의 방향과 위치를 조건에 맞게 배치하는 경우의 수를 구하는 문제

 

문제를 제대로 이해하면

같은 행에서 EW, 같은 열에서 SN 매칭이 일어나면 2개 배치가 가능하고

그렇지 않으면 최대 1개만 배치할 수 있다.

 

따라서 매칭이 없다고 가정하면 (i, j)에 텐트를 배치하는 순간

i행과 j열은 이용불능이 된다.

 

그러면 다음과 같은 함수를 정의해볼 수 있다.

f(i, j) = i행에 빈 자리가 j개 있을 때 배치할 수 있는 경우의 수

 

가능한 전이는

1. 0개 배치한다.

2. 1개 배치한다.

3. 2개 배치한다.

 

0개 배치는 그냥 f(i+1, j)가 되는거고

2개 배치는 EW를 잡아주는 경우뿐이므로 f(i+1, j-2)*((j)*(j-1)/2)가 되겠다.

1개 배치는 N, E, W같은 경우는 배치를 하는 순간 아래에서는 사용하지 못하게 된다.

하지만 S는 아래에서 N을 매치해주는것으로 사용할 수 있게 된다.

각 방향마다 f(i+1, j-1)*j를 하면 해당 방향으로 텐트를 설치하였을 때 매칭이 일어나지 않는 경우가 된다.

사용할 수 있는 자리가 j-1이 되었으니까.

 

이는 방향이 S일때도 마찬가지이다.

S인데 매치가 안되는 경우를 처리해주었으니

S이며 매치가 되는 경우를 처리해주어야 한다.

 

매치가 된다면 내 밑의 n-i개 행 중 하나가 반드시 N으로 맞대어주어야 한다.

해당 행을 고르는 경우의 수는 n-i이고, 자리를 고르는건 j, 내가 자유롭게 선택할 수 있는 행이 하나 줄었으니

f(i+2, j-1)*j*(n-i)가 되겠다.

 

---

 

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

 

트리의 이웃하지 않는 두 정점을 잇는 경로를 간선으로 mst를 구성하는 문제

길이가 4 이상인 경로는 필요하지 않다.

2인 경로와 3인 경로로 분리해서 사용하는 것이 최적이 된다.

만약 해당 경로들을 간선으로 만들어 크루스칼을 돌릴 수 있으면

문제의 답을 구할 수 있을 것이다.

 

- 2인 경로

 

 

정점 u가 매개가 되어

정점 u의 이웃들을 이어줄 것이다. 그러면 2인 경로겠다.

 

u의 이웃집합 a는 u와의 거리에 따라 정렬되어있다.

a끼리 이어주려고 하는데 반드시 a_1 <-> u <-> a_i 이런 꼴이 최적임을 알 수 있다.

 

2인 경로는 O(E)만큼 만들어질 수 있다.

 

- 3인 경로

 

u, v를 잇는 간선 e가 매개가 되어 

정점 u의 이웃과 정점 v의 이웃들을 이어줄 것이다. 그러면 3인 경로겠다.

 

여기서는 a_1 <-> u <-> v <-> b_1 만 필요함을 알 수 있다.

 

만약 a_i가 b_1과 이어져야 할 경우가 있을까?

 

a_i + a_1 > a_i + e + b_1

인 경우가 존재하면 이어져야 할 수도 있다.

ㄷ.ㄷ

a_1 > e + b_1인 경우면 이런 끔찍한 상황이 일어나는게 아닌가? 생각할 수 있지만

v가 빙다리핫바지로보이나

그러면 e가 a_1보다 작으니까 이미 a_i랑 v가 이어져있다.

 

그러면 위의 식은 모순이고

a_i + e > a_i + e + b_1로 다시 적을 수 있다.

0 > b_1 이고 해당 케이스는 존재하지 않음을 알 수 있다.

 

간선 e에 대해 만들어지는 새로운 간선은 최대 1개이므로 O(E)개 만들어진다.

 

결국 만드는 간선은 O(E)개라서 만든 애들로 크루스칼 돌리면 냠냠굿

 

---

 

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

 

bnb2011: 초기에 A랑 D라는 값이 있고 N개 라운드 진행함
매 라운드 시작마다 A가 현재 D 만큼 늘어남
각 라운드에서는 세 가지 선택지 중 하나 골라야 함
공격: A + a_i 데미지만큼 때림
D를 b_i 만큼 늘림
A를 c_i 만큼 늘림
최대 누적 데미지 구하기 N <= 100 나머지 값 모두 <= 10^9 

 

현재 N번째 라운드라고 가정하자.

지금 적금 넣어봤자 더 때릴 수 있는 기회가 없다.

따라서 N번째 라운드면 반드시 때리겠지?

라는 생각에서 출발한다.

 

현재 N-1번째 라운드라고 가정하자.

각 연산에 대해 머리를 굴려보자.

1. (A + a[i]) + (A+D + a[i+1])

2. 0 + (A+(D+b[i]) + a[i+1])

3. 0 + ((A+c[i])+D) + a[i+1])

 

1번 연산은 단순히 데미지만 더 넣는거고,

2번 연산은 미래에 데미지 상승량을 올려준다.

3번 연산은 미래의 데미지를 올려준다.

 

라운드와 데미지 상승량으로 얻는 이득을 케어하기 위하여

다음과 같은 함수를 정의해볼 수 있다.

f(i, j) = [i:N]라운드에서 j번 공격한 경우의 데미지 최대

1번 연산은 f(i+1, j-1)에서 단순히 뎀지만 더해주면 된다.

3번 연산은 f(i+1, j)에서 c[i]만큼 공격력이 높아진 경우니까 j*c[i]만큼 올라간다.

 

2번 연산은 어떨까?

단순히 공격 횟수로는 데미지 상승량의 상승을 알기는 어렵다.

 

다음과 같은 배열이 있다고 가정하자.

[1, 0, 1, 1, 0]

1이 공격한 것일 때, 각 위치에서 펌핑을 받는 횟수는

[1, 0, 3, 4, 0] 이겠다.

 

여기에 버프를 준다고 가정해보자

[0, 1, 0, 1, 1, 0]이 되었고,

펌핑을 받는 횟수는

[0, 2, 0, 4, 5, 0] 이 된다.

 

이미 뒤에서 넣은 데미지는 불변이고, 우리는 펌핑을 받은 횟수*b[i]만 하면 된다.

따라서 f(i, j)에서 버프를 걸어 얻을 수 있는 이득은

f(i+1, j)에서의 (펌핑받는 값+j)*b[i]가 되는 것이고

펌핑받는 값도 상태에 넣어 케어하기 위해

 

f(i, j, k) = f(i, j) = [i:N]라운드에서 j번 공격하고, 버프 기여량이 k일 때 최대 로 정의하게 된다.

f(i, j, k+j) = f(i+1, j, k) + b[i]*k로 전이할 수 있게 된다.

 

k는 커봤자 (n+1)*n/2니까

O(N^4)으로 끗