poj 1976 A Mini Locomotive(가방 01)

제목 링크
Description
A train has a locomotive that pulls the train with its many passenger coaches. If the locomotive breaks down, there is no way to pull the train. Therefore, the office of railroads decided to distribute three mini locomotives to each station. A mini locomotive can pull only a few passenger coaches. If a locomotive breaks down, three mini locomotives cannot pull all passenger coaches. So, the office of railroads made a decision as follows: 
1. Set the number of maximum passenger coaches a mini locomotive can pull, and a mini locomotive will not pull over the number. The number is same for all three locomotives. 
2. With three mini locomotives, let them transport the maximum number of passengers to destination. The office already knew the number of passengers in each passenger coach, and no passengers are allowed to move between coaches. 
3. Each mini locomotive pulls consecutive passenger coaches. Right after the locomotive, passenger coaches have numbers starting from 1. 
제목: 제목의 대략적인 뜻은 n개의 수를 줄 수 있다는 것이다. 그 다음에 세 대의 화물차 헤드가 연속적으로 k대의 차량을 끌 수 있다는 것이다. 이 세 개의 화물차 헤드가 최종적으로 끌 수 있는 가장 큰 승객 수는 얼마냐고 묻는다.
문제풀이 사고방식: 본 인터넷에서 01배낭이라고 했는데 처음에 자기가 생각했을 때 납득이 안 갔어요. 주로 그 연속된 m대 차였어요.
싫어.나중에 다른 사람 코드를 봤어요.드디어 알겠습니다 01 가방입니다.
문제풀이의 방향은sum[]이라는 수조로 연속 m칸의 사람을 저장하는 것이다.그리고 가방01을 시작합니다.사실은 b【i】,01 가방을
왜 4열짜리 그룹을 써야 돼요?첫째, 둘째, 셋째, 각각 표시된 차 한 대, 두 대, 세 대가 끄는 사람이기 때문이다.
어떻게 그 연속 객차의 문제를 끝낼 것인가, 이것이 바로 본 문제의 특수한 점이다.k=i-m로 표시하다
  dp[i][j]=max(dp[i-1][j],dp[k][j-1]+sum[i]);
이 방정식은 매우 중요하다. 의미는 만약에 b[i]가 뽑지 않으면 앞줄을 뽑고 차수가 변하지 않는 값을 뽑는다. 만약에 b[i]가 뽑으려면
b[k][j-1]의 값과 m의 행사가 연속되지 않아 앞의 열에서 차 한 대를 적게 얻었다는 것을 나타낸다.
이것이 바로 이 코드의 사상이다. 코드:

//poj1976 01  
//2013-04-12-16.25
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int a[50005], sum[50005];
int dp[500005][4];

int main()
{
    int t, n, m;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        memset(sum, 0, sizeof(sum));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n-m+1; i++)
        {
            for (int j = i; j < m+i; j++)
            {
                sum[i] += a[j];
            }
        }
        for (int i = 1; i <= n-m+1; i++)
        {
            int k;
            if (i - m < 0)
                k = 0;
            else
                k = i-m;
            for (int j = 1; j <= 3; j++)
            {
                dp[i][j] = max(dp[i-1][j], dp[k][j-1] + sum[i]);
                //        ，       m   
            }
        }
        printf("%d
",dp[n-m+1][3]);
    }
    return 0;
}