A Mini Locomotive POJ - 1976 （动态规划）

A Mini Locomotive

 题目链接：POJ - 1976 

题意：n个连续的车厢，用三个车头带，每个车头最多能带动k个连续的车厢，每个车厢内有不同数量的乘客，问最多能拉走多少乘客；

设dp[i][j]表示第i个车头拉动前j个车厢所能拉走的最大乘客数量；

​
#include <stdio.h>
#include  <string.h>
#include <algorithm>
using namespace std;
int sum[50010], num[50010];
int dp[5][50010];
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		int n;
		sum[0]=0;
		scanf("%d", &n);
		for(int i=1; i<=n; i++){
			scanf("%d", &num[i]);
			sum[i]=sum[i-1]+num[i];
		}
		int k;
		scanf("%d", &k);
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=3; i++){
			for(int j=k; j<=n; j++){
				dp[i][j]=max(dp[i][j-1], dp[i-1][j-k]+sum[j]-sum[j-k]);
			}
		}
		printf("%d\n", dp[3][n]);
	}
	return 0;
}

​