| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 2485 | Accepted: 1388 |
Description
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
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.
Output
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个连续的车厢，这里我们把只要存在连续的m个车厢的就看成一个物品。相当于往背包容量为3的背包里面放物品所得的最大价值量。但是这里注意每连续的m个车厢为一个物品，f[i][j] = max(f[i - 1][j],f[i - m][j - 1] + sum[i] - sum[i - m]); 这里对于每个物品要么不放，要么就是放（放连续的m个车厢）
sum[i] = a[0] + a[1] + ... + a[i];
之前看到这个解题思路感觉一点有疑问：会不会有重复，第一节拉1，2；第二节拉2,3这样的，最后结论是不会;因为不取这个车厢的话，那必然就是【i-1】【j】,如果取的话那么肯定就是【i-m】【j-1】,跳到了i-m了，所以不会重，太弱了，其实这道题也挺简单，就是不会，弱
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int MAX = + ;
int dp[MAX][],sum[MAX],a[MAX];
int main()
{
int t,n,m;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
memset(dp, , sizeof(dp));
memset(sum, , sizeof(sum));
for(int i = ; i <= n; i++)
scanf("%d", &a[i]);
for(int i = ; i <= n; i++)
sum[i] = sum[i - ] + a[i];
scanf("%d", &m);
int tp;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= ; j++)
{
if(i < m) //因为最多是m节，不足m也是可以的，需要处理一下
{
tp = ;
}
else
tp = i - m;
dp[i][j] = max(dp[i - ][j], dp[tp][j - ] + sum[i] - sum[tp]);
}
}
printf("%d\n", dp[n][]);
}
return ;
}