题意分析

题目描述了一列火车，由一台机车牵引多节旅客车厢。为了应对机车故障，铁路部门决定配备三台小型机车，每台小型机车最多牵引连续的m节车厢。目标是选择三台小型机车牵引的连续车厢段，使得这三段车厢的乘客总数最大。 输入数据： 测试用例数量t。 每个测试用例包含： 车厢数量n。 每节车厢的乘客数w[i]。 每台小型机车最多牵引的车厢数m。

约束条件： 车厢数量n ≤ 50,000。 每节车厢的乘客数 ≤ 100。 每台小型机车最多牵引的车厢数m ≤ n/3。

目标： 选择三个不重叠的连续车厢段，每段长度不超过m，使得这三段的总乘客数最大。

解题思路

前缀和数组：为了快速计算任意连续车厢段的乘客总数，预先计算前缀和数组v，其中v[i]表示前i节车厢的乘客总数。

1。动态规划： 定义dp[i][j]表示前i节车厢中选择j段连续车厢段的最大乘客总数。

2.状态转移方程： 如果不选择第i节车厢作为当前段的结尾，则$dp[i][j] = dp[i-1][j]$。 如果选择第i节车厢作为当前段的结尾，则$dp[i][j] = dp[i-m][j-1] + (v[i] - v[i-m])$。

最终结果为$dp[n][3]$，即前n节车厢中选择3段的最大乘客总数。

代码实现

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
	int n,t,w[60000],v[60000],dp[80000][4],m,i,j;
	cin>>t;
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		cin>>n;
		for(i=1;i<=n;i++)
		{
			cin>>w[i];
			v[i]=v[i-1]+w[i];//v[i]存储的是前i节车厢所能承载的总容量。
		}
		cin>>m;
		for(i=m;i<=n;i++)
			for(j=3;j>=1;j--)
				dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+v[i]-v[i-m]);
		cout<<dp[n][3]<<endl;
	}
	return 0;
}