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;
}