백준13974 파일합치기2

작성일 | In

문제 링크

  • http://icpc.me/13974

문제 출처

  • 2015 ACM-ICPC 대전 인터넷 예선 F번

사용 알고리즘

  • DP
  • Knuth Optimization

시간복잡도

  • O(2)

풀이

이 문제는 (여기)에 있는 문제의 입력을 키워놓은 문제입니다.
입력이 최대 5000이기 때문에 O(n2)으로 풀어야합니다.

(이 글) 에 나와있는 최적화 기법을 사용합니다.

dp[i][j] = min(dp[i][k] + dp[k+1][j]) + s[j] - s[i-1]
위 식에서 s[j] - s[i-1]을 C[i][j]라고 잡으면, C[i][j]는 i부터 j번째까지의 파일을 합치는 비용이 됩니다.
D[i][j] = dp[i+1][j] 라고 정의합시다.

dp[i+1][j] = min(dp[i+1][k] + dp[k+1][j]) + C[i][j] 즉, D[i][j] = min(D[i][k] + D[k][j]) + C[i+1][j]

C[i][j]는 i번째부터 j번째까지의 양수의 합이기 때문에 사각부등식과 단조성을 모두 만족합니다.
그러므로 knuth Optimization을 적용할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int dp[510][510], K[510][510];

void solve(int n){
	vector<int> v(n+1), s(n+1);

	for(int i=1; i<=n; i++) cin >> v[i], s[i] = s[i-1] + v[i];
	for(int i=1; i<=n; i++) dp[i-1][i] = 0, K[i-1][i] = i;

	for(int m=2; m<=n; m++){
		for(int i=0; m+i<=n; i++){
			int j = i+m; dp[i][j] = 1e9+7;
			for(int k=K[i][j-1]; k<=K[i+1][j]; k++){
				int now = dp[i][k] + dp[k][j] + s[j] - s[i];
				if(dp[i][j] > now){
					dp[i][j] = now; K[i][j] = k;
				}
			}
		}
	}

	cout << dp[0][n] << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		solve(n);
	}
}