第十一周D题 A Mini Locomotive

A Mini Locomotive

（01背包问题，可以先温习一下01背包）

题目：
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.

For example, assume there are 7 passenger coaches, and one mini locomotive can pull a maximum of 2 passenger coaches. The number of passengers in the passenger coaches, in order from 1 to 7, is 35, 40, 50, 10, 30, 45, and 60.

If three mini locomotives pull passenger coaches 1-2, 3-4, and 6-7, they can transport 240 passengers. In this example, three mini locomotives cannot transport more than 240 passengers.

Given the number of passenger coaches, the number of passengers in each passenger coach, and the maximum number of passenger coaches which can be pulled by a mini locomotive, write a program to find the maximum number of passengers which can be transported by the three mini locomotives.
输入：
The first line of the input contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows:
The first line of the input file contains the number of passenger coaches, which will not exceed 50,000. The second line contains a list of space separated integers giving the number of passengers in each coach, such that the ith number of in this line is the number of passengers in coach i. No coach holds more than 100 passengers. The third line contains the maximum number of passenger coaches which can be pulled by a single mini locomotive. This number will not exceed 1/3 of the number of passenger coaches.
输出：
There should be one line per test case, containing the maximum number of passengers which can be transported by the three mini locomotives.
样例：
输入：
1
7
35 40 50 10 30 45 60
2
输出：
240
——————————————————————————————————————

题意：总共有3个火车头，给你两个数n，m，n代表有n节车厢，m代表一个火车头最多能拉m节车厢；并输入n个数据代表第n节车厢所能拉的乘客人数，请你通过计算，求出最多所能拉的乘客人数。

思路：
//可看成01背包问题
/*
m代表最多能拉几节车厢，所以把每一个挨着的m
节车厢当成一个整体，计算这个整体所能拉的人数；
当来到一个m节车厢的面前时，有两种选择：选择拉
这个整体或者不拉这个整体；肯定取两种情况下所能拉的乘客最多的那一种了，后面就需要用动态方程计算哪一种方式所能拉的乘客最多。
这个动态方程和01背包的动态方程思路一样：
dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m])。
dp[i-1][j]代表不拉当前位置的那个车厢，所以就等于
在上一节车厢时所拉的乘客数；
dp[i-m][j-1]+a[i]-a[i-m]代表拉当前位置的那个车厢，
则就等于这个整体之前(i-m)并把当前位置的火车头分配给当前位置的m节车厢(j-1)时所拉的乘客数加上当前m个车厢所拉乘客数。
再解释一下：i代表当前模拟到了第几节车厢；
j代表当前用到了第几节车厢；
当然，当当前位置的车厢数小于最大所能拉的车厢数，为了计算方便，就把三个火车头所能拉的最多数量变为当前所经过的车厢数；例如：当前站在第二节车厢面前，就只能拉前两节车厢，所以当j=1,2,3时dp数组记录的都是前两节车厢所能拉的人数。
最后用maxx记录最大值。
*/
——————————————————————————————————————
AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,maxx,a[50010];
int dp[50010][100];
int main()
{
    int t,i,j;
    scanf("%d",&t);
    while(t--)
    {
        maxx=0;//记录最大值
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i]+=a[i-1];//求前n项和
        }
        scanf("%d",&m);
        for(i=m;i<=n;i++)
        {
            for(j=1;j<=3;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m]);
                //动归方程
                if(dp[i][j]>maxx)
                {
                    maxx=dp[i][j];
                }
            }
        }
        printf("%d\n",maxx);
    }
    return 0;
}
//可看成01背包问题
/*
m代表最多能拉几节车厢，所以把每一个挨着的m
节车厢当成一个整体，计算这个整体所能拉的人数；
当来到一个m节车厢的面前时，有两种选择：选择拉
这个整体或者不拉这个整体；肯定取两种情况下所能
拉的乘客最多的那一种了，后面就需要用动态方程计
算哪一种方式所能拉的乘客最多。
这个动态方程和01背包的动态方程思路一样：
dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m])。
dp[i-1][j]代表不拉当前位置的那个车厢，所以就等于
在上一节车厢时所拉的乘客数；
dp[i-m][j-1]+a[i]-a[i-m]代表拉当前位置的那个车厢，
则就等于这个整体之前(i-m)并把当前位置的火车头分配
给当前位置的m节车厢(j-1)时所拉的乘客数加上当前m个
车厢所拉乘客数。
再解释一下：i代表当前模拟到了第几节车厢；
            j代表当前用到了第几节车厢；
当然，当当前位置的车厢数小于最大所能拉的车厢数，为了
计算方便，就把三个火车头所能拉的最多数量变为当前所经
过的车厢数；例如：当前站在第二节车厢面前，就只能拉前
两节车厢，所以当j=1,2,3时dp数组记录的都是前两节车厢所
能拉的人数。
最后用maxx记录最大值。
*/