1988번: 낮잠 시간

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

$O(nb)$

dp1[i][j]: a[1...i]에서 j개 구간을 선택했을 때 구간 i에서 회복하는 최대 피로회복량
dp2[i][j]: a[1...i]에서 j개 구간을 선택했을 때 최대 피로회복량
dp1[i][j]=max(dp2[i-1][j-2],dp1[i-1][j-1])+a[i]
dp2[i][j]=max(dp2[i-1][j],dp1[i][j])

#include<cstdio>
#include<algorithm>
using namespace std;
int dp1[3001][3001], dp2[3001][3001], n, b, a[3001];
int main() {
    scanf("%d%d", &n, &b);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        for (int j = 2; j <= b; j++) {
            dp1[i][j] = max(dp2[i - 1][j - 2], dp1[i - 1][j - 1]) + a[i];
            dp2[i][j] = max(dp2[i - 1][j], dp1[i][j]);
        }
    }
    printf("%d", dp2[n][b]);
    return 0;
}