1121번: 도형

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

$O(nkL)$ // L: 선분의 최대 길이

몇 개의 선분들이 주어졌을 때, 가장 큰 선분길이가 해당 선분을 제외한 나머지 선분들 길이 합보다 크면 이들로 다각형을 만들 수 있다. 이 조건을 만족하는 다각형의 개수는 DP로 구함.

선분의 길이가 오름차순으로 a[1...n]에 주어져 있음.
dp[i][j][k]: a[1...i]에서 j개를 선택하여 합 k를 만드는 경우의 수
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-a[i]]

s[i]: 가장 큰 선분의 길이가 a[i]일 때 만들 수 있는 다각형의 수
s[i] = sum(dp[i-1][k-1][a[i]+1...L*k])
답은 sum(s[2...n])

dp 순서에 따라 선분의 종류에 대한 성분을 제거할 수 있고 L을 넘어가는 선분 합에 대해 L+1로 여기면 아래 소스처럼 O(kL) 크기의 dp table로 해결할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, k, a[51];
long long res, dp[10][50002] = { 1 };
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    scanf("%d", &k);
    for (int i = 1; i < n; i++) {
        for (int j = k - 1; j--;) {
            for (int k = a[n] + 1; k >= 0; k--) {
                int t = k + a[i];
                dp[j + 1][t > a[n] ? a[n] + 1 : t] += dp[j][k];
            }
        }
        for (int j = a[i + 1] + 1; j <= a[n] + 1; j++) res += dp[k - 1][j];
    }
    printf("%lld", res);
    return 0;
}