백준7613 보이 스카우트

작성일 | In

문제 링크

  • http://icpc.me/7613

사용 알고리즘

  • DP
  • Convex Hull

시간복잡도

  • $O(N^4)$

풀이

KOI 2017 공룡 발자국과 비슷한 문제입니다.

일단 Convex Hull의 가장 왼쪽 점이 될 점 $i$를 고정합시다.
$D(i, j) = $ Convex Hull에 마지막으로 추가한 점이 i, j일 때 최대 점 개수로 정의해서 $O(N^3)$ DP를 짤 수 있습니다.

모든 $i$에 대해 $O(N^3)$짜리 DP를 수행해주면 $O(N^4)$에 문제를 풀 수 있습니다.
실제 구현은 Monotone Chain처럼 윗 껍질과 아래 껍질로 분리해서 각각 DP를 구해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<double, double> p;

int ccw(const p &a, const p &b, const p &c){
    double dx1 = b.x - a.x, dy1 = b.y - a.y;
    double dx2 = c.x - b.x, dy2 = c.y - b.y;
    double res = dx1*dy2 - dx2*dy1;
    if(!res) return 0;
    return res > 0 ? 1 : -1;
}

int n; vector<p> v;
int dp[111][111][2], mx = 3;

void f(int st){
    memset(dp, 0, sizeof dp);
    for(int i=st+1; i<n; i++){
        dp[st][i][0] = dp[st][i][1] = 1;
        int up = 1, dw = 1;
        for(int j=st+1; j<i; j++){
            for(int k=st; k<j; k++){
                if(ccw(v[k],v[j], v[i]) == -1){
                    if(dp[k][j][0]) dp[j][i][0] = max(dp[j][i][0], dp[k][j][0]+1);
                }
                else{
                    if(dp[k][j][1]) dp[j][i][1] = max(dp[j][i][1], dp[k][j][1]+1);
                }
            }
            up = max(up, dp[j][i][0]);
            dw = max(dw, dp[j][i][1]);
            mx = max(mx, up+dw);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        double x, y; cin >> x >> y;
        v.emplace_back(x, y);
    }
    sort(all(v));

    for(int i=0; i<n-1; i++) f(i);
    cout << mx;
}