解題區/解題區 - UVa

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;
}