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 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
Sample Input
1 7 35 40 50 10 30 45 60 2
Sample Output
240
题意:
某个车站有N个火车车厢,编号为1~N,每个车厢上有x个人。
这个车站还有三个火车头,他们能拉最多m个车厢(m<=N/3),而且这m个车厢的编号要连续的。问这三个火车头最多能拉多少个人。
参考博客:
https://blog.csdn.net/cttacm/article/details/45565447
我的代码:
1 #include<stdio.h> 2 #include<iostream> 3 #include<cmath> 4 #include<string.h> 5 #include<iomanip> 6 using namespace std; 7 #define inf 0x3f3f3f3f 8 9 int a[5050]; 10 int sum[5050]; 11 int dp[5050][4]; 12 int main() 13 { 14 std::ios::sync_with_stdio(false); 15 cin.tie(0); 16 cout.tie(0); 17 int tt; 18 cin>>tt; 19 while(tt--) 20 { 21 memset(a,0,sizeof(a)); 22 memset(sum,0,sizeof(sum)); 23 memset(dp,0,sizeof(dp)); 24 int n; 25 cin>>n; 26 for(int i=1; i<=n; i++) 27 { 28 cin>>a[i]; 29 sum[i]=sum[i-1]+a[i]; 30 } 31 int k; 32 cin>>k; 33 //int maxx=-inf; 34 for(int i=k; i<=n; i++) 35 { 36 for(int j=3; j>=1; j--) 37 { 38 dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+(sum[i]-sum[i-k])); 39 } 40 // maxx=max(dp[i],maxx); 41 } 42 cout<<dp[n][3]<<endl; 43 } 44 return 0; 45 }