POJ1836 Alignment

原题链接:POJ1836

题目大意:最长上升子序列模型。

LIS

正反 LIS,类似,AcWing 482. 合唱队形 ,本题,而最高处可以有两个相同高度。

 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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
double a[N];
int f[N], g[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        }
    }
    for (int i = n; i; i--)
    {
        g[i] = 1;
        for (int j = n; j > i; j--) {
            if (a[j] < a[i])
                g[i] = max(g[i], g[j] + 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            res = max(res, f[i] + g[j]);
        }
    }
    cout << n - res << endl;
    return 0;
}
updatedupdated2020-05-192020-05-19
加载评论
点击刷新