题目
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:
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.
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int []a=new int [60000];
int t,n,m;
t=sc.nextInt();
while(t-->0)
{int [][]dp=new int[60000][10];
int []sum=new int [60000];
n=sc.nextInt();
for(int i = 1; i <= n; i++)
a[i]=sc.nextInt();
for(int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + a[i];
m=sc.nextInt();
int yjl;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 3; j++)
{
if(i < m)
{
yjl = 0;
}
else
yjl = i - m;
dp[i][j] =Math.max(dp[i - 1][j], dp[yjl][j - 1] + sum[i] - sum[yjl]);
}
}
System.out.println(dp[n][3]);
}
}
}