继续简单的背包入门题，原谅我当时的无知。
代码里面重要部分都有注释。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 50100
int a[N];
int dp[4][N];
int b[N];
int main()
{
int n;
cin >> n;
while(n--)
{
int m;
cin >> m;
int sum = 0;
for(int i=1; i<=m; ++i)
{cin >> a[i];
sum += a[i];
}
int t;
cin >> t;//t是其长度;
int g = m-t+1;
memset(b,0,sizeof(b));
if(t*3 >= m)
{
cout << sum <<endl;
continue;
}
for(int i=1; i<=t; ++i)
for(int j=1; j<=g; ++j)
b[j] += a[i+j-1];
for(int i=0; i<=g; ++i)
dp[0][i] = 0;//d[i][j] i表示已经给几个车头装上了车厢， j表示第i个车头的装的是从j开始的车厢。
for(int i=1; i<=3; ++i)
for(int j=t*(i-1)+1; j<=g-(3-i)*t; ++j )
{
if(i == 1)
dp[i][j] = b[j];
else
{//j = 5, j = 6;
dp[i][j] = dp[i-1][j-t] + b[j];
for(int k=(i-2)*t+1; k < j-t; ++k)
if(dp[i-1][k] + b[j] > dp[i][j])
dp[i][j] = dp[i-1][k] + b[j];
}
}
int ma = 0;
for(int j=t*2+1; j<=g; ++j)
if(ma < dp[3][j])
ma = dp[3][j];
cout << ma<<endl;
}
return 0;
}