poj 1976 A Mini Locomotive

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个车厢。求出每个数后的n（n为车头能拉车厢的最大数）个数的和。而后对于每节车厢的拉与不拉取决于当前车头所拉的人数。由此可得到状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-n][j-1]+d[i]);数组d中记录的是每个数之后连续n个数的和

#include<stdio.h>
#include<string.h>
int main()
{
int i,j,k,m,n,t;
int a[50010];
int b[50010];
int c[50010];
int dp[50000][4];
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
for(i=1;i<=m;i++)
  scanf("%d",&a[i]);
scanf("%d",&n);
memset(dp,0,sizeof(dp));
memset(b,0,sizeof(b));
x=0;
for(i=1;i<=m;i++)
{
           x+=a[i];
           c[i]=x;
           if(i>=n)
b[i-n]=c[i]-c[i-n];
   }
   for(i=0;i<m;i++)
   {
    for(j=3;j>0;j--)
    {
if(dp[i-1][j]<dp[i-n][j-1]+b[i])
    {
    dp[i][j]=dp[i-n][j-1]+b[i];
}
else
{
dp[i][j]=dp[i-1][j];
}
}
} 
        printf("%d\n",dp[m-1][3]);
    } 
    return 0;
}

考虑本题时间，想到了动态规划，也想到了求每个数之后连续n个数的和，但是对于找到三数和的最大值还是没有头绪。无奈之下，看了题解。知道了思路。现在在想，每个动态规划的题都是找到状态转移方程，而对于状态转移方程的寻找就是对于当前状态的判断，加还是不加。在看清数据的组成部分之后，做出判断，确定储存方式，便于状态转移方程的寻找，以及代码的进行，再根据状态转移方程写出主循环代码。