題目： UVa - 11790 - Murcia’s Skyline

題目說明

依序給一些建築物的高及重量，求建築物高度嚴格遞增且最寬的寬度，及建築物高度嚴格遞減且最寬的寬度。

Input： 第一個整數 T，表示有 T 組測資，每組測資第一個整數 n，表示有 n 個建築物，後面 n 個數字為建築物的高度，再後面 n 個數字為建築物的寬度。

Output： 輸出 LIS 及 LDS 的寬度，若 LIS 較大則先輸出 LIS，否則先輸出 LDS。

解題思路

使用 DP 找出 LIS 及 LDS 即可，記得 LIS[i] 及 LDS[i] 要初始化為 wides[i] 而不是 1。

參考解法

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
#include <bits/stdc++.h>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int Case;
int T;
int n;
int mxLIS;
int mxLDS;
int heights[10000];
int wides[10000];
int LIS[10000];
int LDS[10000];

void read()
{
    mxLIS = mxLDS = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> heights[i];
    for (int i = 0; i < n; ++i) cin >> wides[i], LIS[i] = LDS[i] = wides[i];
}

void solve()
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            // 若 i 能接在 j 後面 ( LIS )
            if (heights[i] > heights[j]) LIS[i] = max(LIS[j] + wides[i], LIS[i]);
            // 若 i 能接在 j 後面 ( LDS )
            if (heights[i] < heights[j]) LDS[i] = max(LDS[j] + wides[i], LDS[i]);
        }
        mxLIS = max(LIS[i], mxLIS);
        mxLDS = max(LDS[i], mxLDS);
    }

    cout << "Case " << ++Case << ". ";
    if (mxLIS >= mxLDS) cout << "Increasing (" << mxLIS << "). Decreasing (" << mxLDS << ").\n";
    else cout << "Decreasing (" << mxLDS << "). Increasing (" << mxLIS << ").\n";
}

int main()
{
    cin >> T;
    while (T--)
    {
        read();
        solve();
    }
}