2673번: 교차하지 않는 원의 현들의 최대집합

https://www.acmicpc.net/problem/2673


$O(n+p^3)$

#include<stdio.h>
#define max(x,y) x>y?x:y
int n, dp[101][101], a[101][101];
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i < n; i++) scanf("%d %d", &x, &y), a[x][y] = a[y][x] = 1;
    for (int i = 1; i <= 100; i++)
        for (int j = i; j; j--)
            for (int k = j; k <i; k++)
                dp[j][i] = max(dp[j][i], dp[j][k] + dp[k][i] + a[j][i]);
    printf("%d", dp[1][100]);
    return 0;
}

할거
p^2 최적화