1462번: 퀴즈쇼

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


$O(n)$

a[i]: i번 문제 점수
b[i]: i번 문제 보너스 점수
s[i]: sum(a[1..i])
dp[i][j]: 1..i번 문제를 풀었고 j개의 쿠폰을 가지고 있을 때 최대 점수
dp[i][0] = max(max(dp[i-1][0..m-1] - a[i]), dp[i-1][m-1] + a[i] + b[i])
dp[i][j](j>0) = dp[i-1][j-1] + a[i]

다음과 같이 p[i], q[i]를 정의하자.
p[i] = max(dp[i][0..m-1])
q[i] = dp[i][0]

dp[i-1][m-1] + a[i] + b[i] = dp[i-m][0] + s[i] - s[i-m] + b[i] 이므로
q[i] = max(p[i-1] - a[i], q[i-m] + s[i] - s[i-m] + b[i])  ...  (*)
또한,
max(p[i-1] + a[i], q[i])
= max(max(dp[i-1][0..m-1]+a[i]), q[i])
= max(dp[i][1..m-1], max(dp[i-1][m-1]+a[i], q[i]))
= max(dp[i][1..m-1], q[i])  ...  (*)에 의해
= p[i]

정리하면
p[i] = max(p[i-1] + a[i], q[i])
q[i] = max(p[i-1] - a[i], q[i-m] + s[i] - s[i-m] + b[i])

답은 p[n]

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[500001];
long long s[500001], q[500001], p;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), s[i] = s[i - 1] + a[i];
    for (int i = 1, b; i <= n; i++) {
        scanf("%d", &b);
        q[i] = i < m ? p - a[i] : max(p - a[i], q[i - m] + s[i] - s[i - m] + b);
        p = max(p + a[i], q[i]);
    }
    printf("%lld", p);
    return 0;
}

11066번: 파일 합치기

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


p[i]: i번째 파일 크기

$O(n^3)$

dp[i][j]: p[i...j]를 합칠때 드는 최소 비용
dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum(p[i...j])

#include<cstdio>
int t, n, s[501], dp[501][501];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
        for (int i = 2; i <= n; i++) {
            for (int j = i; --j;) {
                dp[j][i] = 2e9;
                for (int k = j; k <= i; k++)
                    if (dp[j][i] > dp[j][k] + dp[k + 1][i]) dp[j][i] = dp[j][k] + dp[k + 1][i];
                dp[j][i] += s[i] - s[j - 1];
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}

$O(n^2)$

a<=b<=c<=d인 a,b,c,d에 대해
1) sum(p[a...c])+sum(p[b...d])<=sum(p[b...c])+sum(p[a...d])
2) sum(p[b...c])<=sum(p[a...d])
이므로 knuth optimization을 적용할 수 있다.

dp[i][j]: p[i+1...j]를 합칠 때 드는 최소 비용
opt[i][j]: dp[i][j]를 구할 때 사용한 최적 k

#include<cstdio>
int t, n, dp[501][501], opt[501][501], s[501];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", s + i);
            s[i] += s[i - 1];
            opt[i - 1][i] = i;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j + i <= n; j++) {
                dp[j][j + i] = 2e9;
                for (int k = opt[j][j + i - 1]; k <= opt[j + 1][j + i]; k++) {
                    if (dp[j][j + i]>dp[j][k] + dp[k][j + i]) {
                        dp[j][j + i] = dp[j][k] + dp[k][j + i];
                        opt[j][j + i] = k;
                    }
                }
                dp[j][j + i] += s[j + i] - s[j];
            }
        }
        printf("%d\n", dp[0][n]);
    }
    return 0;
}