A Mini Locomotive POJ

Mini Locomotive POJ"/>

A Mini Locomotive POJ

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;
}​