2451번: 모둠

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


$O(n^2)$

dp[i]: 1~i 사이 관계만 존재할 때 최소 분할 점수
dp[0]=0
dp[i]=min(j<=i)(dp[j-1]+(j~i 모둠 내 존재하지 않는 관계 수)+(1~j-1과 j~i 사이 존재하는 관계 수))

#include<cstdio>
int n, dp[3001], fr[3001], f[3001], b[3001], l[3001][3001], lcnt[3001], r[3001], rcnt;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
        while (scanf("%d", &x) && x) x < i ? f[i]++ : l[x][lcnt[x]++] = i;
    for (int i = 1; i <= n; i++) {
        while (lcnt[i]--) b[l[i][lcnt[i]]]++;
        dp[i] = 1e9;
        for (int j = i, s = 0; j; j--) {
            s += f[j] - 2 * b[j] + i - j;
            if (dp[i] > dp[j - 1] + s) {
                dp[i] = dp[j - 1] + s;
                fr[i] = j - 1;
            }
        }
    }
    printf("%d\n", dp[n]);
    for (int i = n; i; i = fr[i]) r[rcnt++] = i - fr[i];
    printf("%d ", rcnt);
    while (rcnt--) printf("%d ", r[rcnt]);
    return 0;
}