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\n",dp[n-m+1][3]);
    }
    return 0;
}