Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Building

Category: JOI Tag: dp

Building

問題概要


最長増加部分列の長さを求めよ.

解法


DPする.
制約の関係上O(n^2)でも通るがO(n log n)の有名なDP.

コード


(Building.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

int n, h[1024], dp[1024];

int solve()
{
        for (int i = 0; i < n; i++) dp[i] = inf;
        for (int i = 0; i < n; i++) *lower_bound(dp,dp+n,h[i]) = h[i];
        return lower_bound(dp,dp+n,inf)-dp;
}

void input()
{
        cin >> n;
        for (int i = 0; i < n; i++) cin >> h[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments