2228번: 구간 나누기

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


$O(nm)$

dp[n][m]: a[1...n]으로 m개의 구간을 만들어서 가능한 구간들 최대 합

dp[n][m]=max(dp[n-1][m],max(k)(dp[k-1][m-1]+s[i]-s[k]))

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[101][51], s[101], n, m;
int main() {
    scanf("%d%d", &n, &m);
    fill(&dp[0][1], &dp[0][m + 1], -1e9);
    for (int i = 1; i <= n; i++) {
        scanf("%d", s + i);
        s[i] += s[i - 1];
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            for (int k = i - 1; k / 2 >= j - 1; k--) dp[i][j] = max(dp[i][j], (j>1 ? dp[k - 1][j - 1] : 0) + s[i] - s[k]);
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}