POJ1976-A Mini Locomotive-dp

题意：
某个车站有N个火车车厢，编号为1～N，每个车厢上有x个人。

这个车站还有三个火车头，他们能拉最多m个车厢（m<=N/3），而且这m个车厢的编号要连续的。问这三个火车头最多能拉多少个人。

参考博客：
https://blog.csdn.net/cttacm/article/details/45565447

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<string.h>
#include<iomanip>
using namespace std;
#define inf 0x3f3f3f3f

int a[5050];
int sum[5050];
int dp[5050][4];
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin>>tt;
    while(tt--)
    {
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        int n;
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        int k;
        cin>>k;
        //int maxx=-inf;
        for(int i=k; i<=n; i++)
        {
            for(int j=3; j>=1; j--)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+(sum[i]-sum[i-k]));
            }
            //      maxx=max(dp[i],maxx);
        }
        cout<<dp[n][3]<<endl;
    }
    return 0;
}