ALOHA 월반 4주차 - DP (Interval DP / LIS / LCS)

1. [22971] 증가하는 부분 수열의 개수 (Silver II)

의도한 태그: Longest Increasing Subsequence

 

\( D_{i} = A_{i} \)로 끝나는 LIS의 개수를 정의하면, 점화식은 아래와 같이 적어볼 수 있습니다.

• \( j < i \)면서 \( A_{j} < A_{i} \)인 \( j \)에 대해, \( \sum D_{j} \)

const ll mod= 998244353;
int arr[5020];
ll dp[5020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		dp[i] = 1;
		for (int j = 1; j < i; j++){
			if (arr[j] >= arr[i]){ continue; }
			dp[i] += dp[j]; dp[i] %= mod;
		}
	}
	for (int i = 1; i <= n; i++){ cout << dp[i] << ' '; }
}

2. [2565] 전깃줄 (Gold V)

의도한 태그: Longest Increasing Subsequence

 

왼쪽에서 \( i \)번에 연결된 전깃줄이 오른쪽에서는 \( A_{i} \)번에 연결되어있다고 해봅시다.

그럼, 두 전깃줄이 교차하지 않는다는 건 \( i < j \)면 \( A_{i} < A_{j} \)라는 의미가 됩니다.

 

그럼 최대한 많은 전깃줄을 남기려면, \( i < j \)면서 \( A_{i} < A_{j} \)인 \( A_{i} \)를 최대한 길게 해야 하므로

이 문제는 그냥 LIS를 구하는 문제가 됩니다.

const int N = 500;
int arr[520], dp[520];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		int a, b; cin >> a >> b; arr[a] = b;
	}
	int ans = 0;
	for (int i = 1; i <= N; i++){
		if (arr[i] == 0){ continue; }
		dp[i] = 1;
		for (int j = 1; j < i; j++){
			if (arr[j] == 0){ continue; }
			if (arr[j] < arr[i]){ dp[i] = max(dp[i], dp[j]+1); }
		}
		ans = max(ans, dp[i]);
		//cout << arr[i] << " | DP " << i << " = " << dp[i] << endl;
	}
	cout << n-ans;
}

3. [25343] 최장 최장 증가 부분 수열 (Gold V)

의도한 태그: Longest Increasing Subsequence

 

\( D_{y, x} = (y, x) \)를 끝으로 하는 LIS의 최대 길이 를 정의해봅시다.

 

그럼, 점화식은 아래 값들의 최댓값이 됩니다. (기본값 = 1)

• \( i \lt y, j \lt x \)에 대해 \( A_{i, j} \lt D_{y, x} \)라면: \( D_{i, j} + 1 \)

 

문제의 답은 \( \max_{1 \le x, y \e N} D_{y, x} \)가 됩니다.

 

+ 시간복잡도는 \( O(N^4) \)이지만, 실제로는 \( O(N^4 / 4) \)에 가까워서 2500만 회의 연산으로 AC를 받을 수 있습니다.

int arr[120][120], dp[120][120];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			int mx = 0;
			for (int y = 1; y <= i; y++){
				for (int x = 1; x <= j; x++){
					if (arr[y][x] < arr[i][j]){ mx = max(mx, dp[y][x]); }
				}
			}
			dp[i][j] = mx+1; ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
}

4. [9252] LCS 2 (Gold IV)

의도한 태그: Longest Common Substring

 

\( D_{i, j} = S_{1} \)의 첫 \( i \) 글자와 \( S_{2} \)의 첫 \( j \)글자로 만들 수 있는 LCS의 길이 를 정의해봅시다.

 

그럼, 점화식은 아래와 같이 나오게 됩니다.

• \( S_{1} \)의 \( i \)번째 글자를 무시하고 LCS를 구해보기: \( D_{i-1, j} \)
• \( S_{2} \)의 \( j \)번째 글자를 무시하고 LCS를 구해보기: \( D_{i, j-1} \)
• \( S_{1} \)의 \( i \)번째 글자와 \( S_{2} \)의 \( j \)번째 글자를 LCS에 매칭시켜보기: \( D_{i-1, j-1} + 1 \)
  • 이 경우는 \( S_{1, i} = S_{2, j} \)여야 합니다.

위 3가지 경우 중 가장 큰 값을 들고 오면 점화식이 완성됩니다.

 

초항은, 한 쪽 문자열이 비어있을 때 \( D_{0, i} = D_{i, 0} = 0 \)이고,

 

문제의 답은 \( D_{|S_{1}|, |S_{2}|} \)가 됩니다.

 

그럼 실제 LCS는 어떻게 구할까요?

우선 \( p_{1}, p_{2} \)를 준비한 뒤, 아래와 같이 역추적을 돌려주면 됩니다.

• \( S_{1, p_{1}} = S_{2, p_{2}} \text{ and } D_{p_{1}-1, p_{2}-1} + 1 \): LCS의 맨 앞에 \( S_{1, p_{1}} \)를 추가 후, \( p_{1}, p_{2} \)를 각각 1씩 감소
• 그 외의 경우: \( D_{p_{1}-1, p_{2}} \)와 \( D_{p_{1}, p_{2}-1} \) 중 더 큰 값을 가지고 있는 상태로 가면 됩니다.

int dp[1020][1020];

void Main(){
	string s1, s2; cin >> s1 >> s2; int l1 = s1.size(), l2 = s2.size();
	s1 = " " + s1; s2 = " " + s2;
	for (int i1 = 1; i1 <= l1; i1++){
		for (int i2 = 1; i2 <= l2; i2++){
			dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1]);
			if (s1[i1] == s2[i2]){ dp[i1][i2] = max(dp[i1][i2], dp[i1-1][i2-1] + 1); }
		}
	}
	cout << dp[l1][l2] << endl;
	int p1 = l1, p2 = l2; stack<char> stk;
	while (p1 > 0 && p2 > 0){
		if (s1[p1] == s2[p2] && dp[p1-1][p2-1]+1 == dp[p1][p2]){
			stk.push(s1[p1]); p1 -= 1; p2 -= 1;
		}
		else{
			if (dp[p1-1][p2] > dp[p1][p2-1]){ p1 -= 1; }
			else{ p2 -= 1; }
		}
	}
	while (!stk.empty()){ cout << stk.top(); stk.pop(); }
}

5. [11066] 파일 합치기 (Gold III)

의도한 태그: Interval DP

 

\( D_{st, ed} = [st, ed] \) 구간의 파일을 하나로 합치는데 드는 총 비용 을 정의해봅시다.

 

그럼 점화식은 아래와 같이 계산해볼 수 있습니다.

• \( [st, st] \)를 합치고 \( [st+1, ed] \)를 합친 뒤, 이 두 파일을 합치기: \( D_{st, st} + D_{st+1, ed} + \sum_{i=st}^{st} A_{i} + \sum_{i=st+1}^{ed} A_{i} \)
• \( [st, st+1] \)을 합치고 \( [st+2, ed] \)를 합친 뒤, 이 두 파일을 합치기: \( D_{st, st+1} + D_{st+2, ed} + \sum_{i=st}^{st+1} A_{i} + \sum_{i=st+2}^{ed} A_{i} \)
• ...
• \( [st, ed-1] \)을 합치고 \( [ed, ed] \)를 합친 뒤, 이 두 파일을 합치기: \( D_{st, ed-1} + D_{ed, ed} + \sum_{i=st}^{ed-1} A_{i} + \sum_{i=ed}^{ed} A_{i} \)

물론 저걸 저대로 구현하라고 하면 하기 싫을테니, 이를 간단하게 바꿔봅시다.

 

우선, 위 점화식을 아래와 같이 나타내볼 수 있습니다.

\( \min_{st \le k \lt ed} \left(D_{st, k} + D_{k+1, ed} + \sum_{i=st}^{k} A_{i} + \sum_{i=k+1}^{ed} A_{i} \right) \)

그런데 수열에서 \( \sum_{i=st}^{k} A_{i} + \sum_{i=k+1}^{ed} A_{i} = \sum_{i=st}^{ed} A_{i} \)이므로,

\( \min_{st \le k \lt ed} \left(D_{st, k} + D_{k+1, ed} + \sum_{i=st}^{ed} A_{i} \right) \)으로 줄여써볼 수 있습니다.

 

물론 구간의 합을 구하는 건 시간이 오래 걸리니, 실제로는 누적합으로 빠르게 구해주면 됩니다.

 

초항은 간단하게 \( D_{i, i} = 0 \)이고, 문제의 답은 \( D_{1, N} \)이 됩니다.

const ll INF = 1e15;
ll arr[520], prf[520]; ll dp[520][520];
inline ll sum(int st, int ed){ return prf[ed] - prf[st-1]; }

void Main(){
	int t; cin >> t;
	while (t--){
		int n; cin >> n;
		for (int i = 1; i <= n; i++){ cin >> arr[i]; }
		for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
		for (int l = 2; l <= n; l++){
			for (int st = 1; ; st++){
				int ed = st+l-1; if (ed > n){ break; }
				dp[st][ed] = INF; ll val = sum(st, ed);
				for (int k = st; k < ed; k++){
					dp[st][ed] = min(dp[st][ed], dp[st][k]+dp[k+1][ed] + val);
				}
			}
		}
		cout << dp[1][n] << endl;
	}
}

6. [1958] LCS 3 (Gold III)

의도한 태그: Longest Common Substring

 

\( D_{i, j, k} = S_1 \)의 첫 \( i \)글자, \( S_j \)의 첫 \( j \)글자, \( S_k \)의 첫 \( k \)글자로 만들 수 있는 최대 LCS 를 정의해봅시다.

 

그럼, 점화식은 아래와 같은 경우에 대한 값의 최대가 됩니다.

• \( S_1 \)의 \( i \)번째 글자를 무시: \( D_{i-1, j, k} \)
• \( S_2 \)의 \( j \)번째 글자를 무시: \( D_{i, j-1, k} \)
• \( S_3 \)의 \( k \)번째 글자를 무시: \( D_{i, j, k-1} \)
• \( S_{1, i} = S_{2, j} = S_{3, k} \)라면, 저 글자를 원래 LCS에 추가: \( D_{i-1, j-1, k-1} + 1 \)

 

초항은 \( D_{0, j, k} = D_{i, 0, k} = D_{i, j, 0} = 0 \)이고, 답은 \( D_{|S_1|, |S_2|, |S_3|} \)이 됩니다.

int dp[120][120][120];

void Main(){
	string s1, s2, s3;
	cin >> s1 >> s2 >> s3;
	int l1 = s1.size(), l2 = s2.size(), l3 = s3.size();
	for (int i = 0; i <= l1; i++){
		for (int j = 0; j <= l2; j++){
			for (int k = 0; k <= l3; k++){
				if (i*j*k == 0){ dp[i][j][k] = 0; }
				else{
					dp[i][j][k] = max({ dp[i][j][k-1], dp[i][j-1][k], dp[i-1][j][k] });
					if (s1[i-1] == s2[j-1] && s2[j-1] == s3[k-1]){
						dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1]+1);
					}
				}
			}
		}
	}
	cout << dp[l1][l2][l3];
}

7. [24940] Split the GSHS (Gold III)

의도한 태그: Interval DP

 

\( D_{st, ed} = [st. ed] \) 구간의 학생들을 합치면서 떨어뜨릴 수 있는 친밀도 를 정의해봅시다.

 

그럼 점화식은 \( st \le k \lt ed \)인 \( k \)에 대해 아래 값의 최대가 됩니다.

• \( [st, k] \)를 합친 뒤, \( (k, ed] \)를 합치고, 이 둘을 합치기: \( D_{st, k} + D_{k+1, ed} + f([st, k], [k+1, ed]) \)
  • 여기서 함수 \( f \)는 두 학생 무리를 합칠 때 감소시킬 수 있는 친밀도입니다.

 

초항은 \( D_{i, i} = 0 \)이고, 문제의 답은 \( D_{1, N} \)이 됩니다.

ll arr[90], prf[90];
ll dp[90][90];

int sgn(ll x){ return (x > 0) - (x < 0); }
ll sum(int st, int ed){ return prf[ed] - prf[st-1]; }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	for (int len = 2; len <= n; len++){
		for (int st = 1, ed = len; ed <= n; st++, ed++){
			for (int k = st; k < ed; k++){
				ll res = dp[st][k] + dp[k+1][ed];
				if (sgn(sum(st, k)) != sgn(sum(k+1, ed))){
					res -= sum(st, k) * sum(k+1, ed);
				}
				dp[st][ed] = max(dp[st][ed], res);
			}
			//cout << "DP " << st << ' ' << ed << " = " << dp[st][ed] << endl;
		}
	}
	cout << -dp[1][n];
}

8. [7476] 최대 공통 증가 수열 (Gold I)

의도한 태그: Longest Common Substring, Longest Increasing Subsequence

 

우선 \( i \)가 증가하는 순서대로 스위핑을 날리면서, 전역으로 아래 DP를 업데이트해봅시다.

\( D_{j} = B_j \)를 끝으로 하는 LCIS의 최대 길이 (초기값 = 0)

 

그럼, 아래와 같이 DP를 업데이트해볼 수 있습니다.

• \( A_i = B_j \)라면, \( k < j \)이고 \( B_k < B_j \)인 \( k \)에 대해 \( D_j \)를 \( D_k + 1 \)로 업데이트

 

역추적은 \( P_{j, c} = B_j \)를 끝으로 하는 길이 \( c \)의 LCIS에서, \( B_j \) 직전에 나오는 원소(의 인덱스) 를 저장해주면 됩니다.

길이를 같이 저장해줘야 하는데, LIS와는 달리 LCIS는 앞의 원소로 끝내는 LCIS를 더 길게 만들 수 있기 때문입니다.

그런데 그걸 신경 안 썼다가는 역추적 배열이 꼬여버리겠죠.

ll arr[520], brr[520];
int dp[520], pre[520][520];

void Main(){
	int n; cin >> n; for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int m; cin >> m; for (int i = 1; i <= m; i++){ cin >> brr[i]; }
	memset(dp, -1, sizeof(dp)); dp[0] = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (arr[i] != brr[j]){ continue; }
			for (int k = 0; k < j; k++){
				if (k==0 || brr[k] < brr[j]){
					if (dp[j] < dp[k]+1){
						dp[j] = dp[k]+1; pre[j][ dp[j] ] = k;
						//if (j == 4){ cout << "J4 " << dp[j] << ' ' << pre[j] << endl; }
					}
					//cout << "dp " << k << " = " << dp[k] << endl;
				}
			}
			//cout << "DP " << j << " = " << dp[j] << endl << flush;
			//system("pause");
		}
	}
	int ans = 0, ptr = 0;
	//for (int i = 1; i <= n; i++){ cout << arr[i] << ' '; } cout << endl;
	for (int i = 1; i <= m; i++){
		if (dp[i] > ans){
			ans = dp[i]; ptr = i;
		}
		//cout << "DP " << i << ' ' << brr[i] << ' ' << dp[i] << ' ' << pre[i] << endl;
	}
	cout << ans << endl; stack<ll> stk;
	while (ans--){ stk.push(brr[ptr]); ptr = pre[ptr][ans+1]; }
	while (!stk.empty()){ cout << stk.top() << ' '; stk.pop(); }
}

9. [1509] 팰린드롬 분할 (Gold I)

의도한 태그: Interval DP

 

우선 팰린드롬 판별을 위해 아래 DP를 만들어봅시다.

\( P_{st, ed} = S_{st} S_{st+1} \cdots S_{ed} \)가 회문인지 여부

 

그럼 점화식은 아래 방식으로 만들어볼 수 있습니다.

• \( P_{st, ed} \)가 회문이려면, \( S_{st} = S_{ed} \)면서 \( P_{st+1, ed-1} \)여야 한다.

 

초항은 \( P_{i, i} = \text{True}, P_{i, i+1} = (S_{i}=S_{i+1}) \)이 됩니다.

 

근데 이렇게 회문 판별을 해도, 문제는 어떻게 풀어야 할까요?

\( D_{i} = S_1 S_2 \cdots S_i \)를 분할하기 위해 필요한 팰린드롬의 최소 개수

라는 DP를 하나 더 정의해보면, 아래와 같은 점화식을 생각해볼 수 있습니다.

• \( P_{j, i} \)인 \( j (\le i)\)에 대해, \( D_{j-1} + 1 \)의 최솟값

초항은 \( D_0 = 0 \)이고, 문제의 답은 \( D_N \)이 됩니다.

bool pal[2520][2520]; int dp[2520];

void Main(){
	string s; cin >> s; int n = s.size(); s = " " + s;
	for (int i = 1; i <= n; i++){ pal[i][i] = 1; }
	for (int i = 1; i < n; i++){ pal[i][i+1] = (s[i] == s[i+1]); }
	for (int l = 3; l <= n; l++){
		for (int i = 1; i <= n; i++){
			int j = i + l-1; if (j > n){ break; }
			pal[i][j] = (s[i] == s[j] && pal[i+1][j-1]);
		}
	}
	for (int i = 1; i <= n; i++){
		int mn = 1e9;
		for (int j = 0; j < i; j++){
			if (pal[j+1][i]){ mn = min(mn, dp[j]); }
		}
		dp[i] = mn+1;
	}
	cout << dp[n];
}