문제
풀이
- 이 문제는 행렬곱 최적화 문제랑 비슷하다.
- 문제를 분할하여 작은 문제들로 나누고, 그 작은 문제들의 최적해를 합치면서 최적의 결과를 얻는다.
기저조건
- 기저조건은 파일이 하나있는 경우와, 파일이 두개있는 경우로 생각할 수 있다.
분할정복
- 분할은 간단하다. 왼쪽에서부터 분할하면된다.
- 그리고 이 비용을 합치고, 이 구간의 길이를 더해준다.(복사비용)
1
2
3
4
for (int mid = lo; mid < hi; mid++)
{
int cost = dp(v, lo, mid) + dp(v, mid + 1, hi);
ret = min(cost + len[lo][hi], ret);
최적화하기
가장 간단하게 생각할 수 있는 최적화는 길이를 누적합을 통해 미리 계산하는 것이다.(아래 코드에서 길이는 그냥 비용과 같이 업데이트했음)
iterative 방식을 사용하여 재귀호출 제거
코드
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
int cost[502][502];
int len[502][502];
int dp(vector<int> &v, int lo, int hi)
{
if (lo + 1 == hi)
{
len[lo][hi] = v[lo] + v[hi];
return cost[lo][hi] = len[lo][hi];
}
if (lo == hi)
{
len[lo][hi] = v[lo];
return cost[lo][hi] = 0;
}
int &ret = cost[lo][hi];
if (ret != 0)
{
return ret;
}
ret = 1e9;
for (int mid = lo; mid < hi; mid++)
{
int cost = dp(v, lo, mid) + dp(v, mid + 1, hi);
len[lo][hi] = len[lo][mid] + len[mid + 1][hi];
ret = min(cost + len[lo][hi], ret);
}
return ret;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
memset(cost, 0, sizeof cost);
memset(len, 0, sizeof len);
int n;
cin >> n;
vector<int> v;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
v.push_back(a);
}
cout << dp(v, 0, v.size() - 1) << "\n";
}
}