UVa 13017 - Canvas Painting

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 $N$ 塊畫布排成一列,並且目標將每一塊畫布變成不同顏色,每一次可以將一個區間塗成相同顏色,花費便是區間 $C_i$ 總和,請問最少花費為何。

Sample Input

1
2
3
4
5
2
3
7 4 7
4
5 3 7 5

Sample Output

1
2
29
40

Solution

每一次最多完成一個不同顏色的畫布,那麼著色解法看來就是二元樹,每一個畫布處於葉節點,因此最少花費就相當於編碼長度乘上葉權重最少。

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
#include <bits/stdc++.h>
using namespace std;
// Huffman Coding, Greedy
// input A[1...n]
// minimum \sum A[i]*code[i]
int main() {
int testcase;
scanf("%d", &testcase);
while (testcase--) {
int n, x;
long long t;
multiset<long long> S;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &x), S.insert(x);

long long ret = 0;
for (int i = n-2; i >= 0; i--) {
long long a, b;
a = *S.begin();
S.erase(S.begin());
b = *S.begin();
S.erase(S.begin());
ret += a+b;
S.insert(a+b);
}
printf("%lld\n", ret);
}
return 0;
}