백준2673 교차하지 않는 원의 현들의 최대집합

작성일 | In

문제 링크

  • http://icpc.me/2673

문제 출처

  • 1996 KOI 고등부 2번

사용 알고리즘

  • DP

시간복잡도

  • $O(100^3)$

풀이

$i, i+1, i+2, \cdots, j$에 있는 점들을 끝점으로 하면서 교차하지 않는 선분들의 집합의 최대 크기를 $D(i, j)$라고 정의합시다.
$i$와 $j$를 잇는 선분의 존재 여부를 $C(i, j)$라고 하면 $D(i, j) = \max(D(i, k) + D(k, j) + C(i, j))$이므로 $O(X^3)$에 점화식을 계산할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int n, dp[101][101], cost[101][101];

int main() {
    cin >> n;
    for(int i=0; i<n; i++){
    	int a, b; cin >> a >> b; cost[a][b] = cost[b][a] = 1;
	}

    for (int i=1; i<=100; i++)
        for (int j=i; j>=1; j--)
            for (int k=j; k<i; k++)
                dp[j][i] = max(dp[j][i], dp[j][k] + dp[k][i] + cost[i][j]);

    printf("%d", dp[1][100]);
}