poj1976 A Mini Locomotive 【二维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.
Input
    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 i th 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.
Output
    There should be one line per test case, containing the maximum number of passengers which can be transported by the three mini locomotives.
Sample Input

    1
    7
    35 40 50 10 30 45 60
    2

Sample Output

    240

题意：给定n个车厢的乘客数，每个火车头最多能拉的车厢数m（共三个火车头），问，最多能拉的乘客数。

思路：类似于一维01背包，求解将哪些物品放入背包可使容量最大，只不过，此题变形之处是，要求连续m个物品。

背包九讲中关于一维01背包的讲解是：若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。

在一维01背包中，如果不放第i件物品，那么问题就转化为“将第i-1个物品放入容量为v的背包”，价值为dp[i-1][v]，类比此题，如果不将第i个车厢人数放入容量为j的火车，那么问题就转化为将i-1节车厢人数放入容量为j的火车,价值为dp[i-1][j]；如果放第i件物品，那么问题就转化为“将第i-1个物品放入容量为v的背包”，价值为dp[i-1][v-cost]+value,类比此题，如果将第i个车厢人数放入容量为j的火车，那么问题就转化为“将i-m节车厢的人数放入容量为j-1的火车”（因为火车头被占据一个，所以容量减少1），价值为dp[i-m][j-1]+sum[i]-sum[i-m];

数组sum[i]的作用是存储前i节车厢的总人数，方便计算。

总结：万变不离其宗，多思考，多总结，emmm,多写题~~~,i can make it~~~

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define N 50000
int sum[N+10],dp[N+10][5];
int main()
{
	int t,n,m;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(sum,0,sizeof(sum));
		memset(dp,0,sizeof(dp));
		for(int i = 1; i <= n; i ++)
			scanf("%d",&sum[i]);
		scanf("%d",&m);
		for(int i = 2; i <= n; i ++)
			sum[i] += sum[i-1];
		for(int i = m; i <= n;i ++)
		{
			for(int j = 1; j <= 3; j ++)
			{
				dp[i][j] = max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
				//求第i节车厢第j个火车头最大容纳乘客数
				//将前i-1个车厢人数放入有j个火车头的火车
				//将前i-m个车厢人数放入有j-1个火车头的火车 
			}
			
		}
		printf("%d\n",dp[n][3]);//输出容量为3的背包的最大价值 
	}
	return 0;
}