hud 3905 - Sleeping [동적 계획]

제목: 한 수업에 n분이 있는데 만약에 i분에 수업을 들으면 a[i]점을 받을 수 있다. 만약에 잠을 자면 이 점수를 받지 못한다. 한 수업에 적어도 m분은 자야 하며 매번 수업을 들으면 연속적인 시간>=L분이어야 한다. 잠자는 시간은 연속되지 않고 가장 많은 점수를 얻을 수 있다.
문제 풀이:
         1. 다른 사람의 기획 사상을 보면 dp[i][j][0]는 전 i분에 j분을 듣고 i분에 수업을 듣지 않았다는 뜻이고 dp[i][j][1]는 전 i분에 j분을 듣고 i분에 수업을 듣는다는 뜻이다.
         2. 나의 사상은 dp[i][j][0]가 전 i분에 j분을 자고 i분에 잠을 자지 않았다는 것을 나타낸다. dp[i][j][1]는 전 i분에 j분을 자고 i분에 잠을 자고 있다는 것을 의미한다.다음을 수행합니다.
             dp[i][j][1] = max(dp[i-1][j-1][0], dp[i-1][j-1][1]);
             dp[i][j][0] = max(dp[i-L][j][1]+sum[i]-sum[i-L], dp[i-1][j][0]+a[i]);

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1005;

int dp[MAXN][MAXN][2];

int main()
{
    int n, m, L;
    int a[MAXN], sum[MAXN];

    while (scanf("%d %d %d", &n, &m, &L) != EOF)
    {
        for (int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        memset(sum, 0, sizeof(sum));
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=n; i++)
            sum[i] = sum[i-1] + a[i];
        for (int i=1; i<=n; i++)
        {
            if (i >= L)
                dp[i][0][0] = sum[i];  //   i         
            for (int j=1; j<=m && j<=i; j++)
            {
                dp[i][j][1] = max(dp[i-1][j-1][0], dp[i-1][j-1][1]);
                if (i-L >= j)
                    dp[i][j][0] = max(dp[i-L][j][1]+sum[i]-sum[i-L], dp[i-1][j][0]+a[i]);
                    //      ：
                    // dp[i][j][0] = max(dp[i-L][j][1], dp[i-L][j][0]) + sum[i] - sum[i-L];
                    //     .
            }
        }
        printf("%d
", max(dp[n][m][0], dp[n][m][1]));
    }
}