[C++知识库]C. Increase Subarray Sums

题目链接
题意：就是每次加上k个x(k∈[0,n])，然后分别求最大区段和，注意此题加上k个x并不是一个连续的动作，而是单独的，每次加上k个x然后求最大区段和，本来以为是连续的没有写出来。知道这个就很简单了，分别求出为i长度的最大和，然后分别加上n个k即可。
下面是AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5050;
int a[N];
int len[N];//i长度的数组最最大值
int prefix[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(len,-0x3f,sizeof(len));//要注意，凡是涉及到有负数的东西一定要初始设到最小
        memset(prefix,0,sizeof(prefix));
        int n,x;
        cin>>n>>x;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) prefix[i]=prefix[i-1]+a[i];//求一个前缀和
        //for(int i=1;i<=n;i++) printf("%d-->\n",prefix[i]);
        for(int i=1;i<=n;i++)//从i位置开始k长度区间的最大值
        {
            for(int k=1;k<=n;k++)//
            {
                if(i+k-1<=n) len[k]=max(len[k],prefix[i+k-1]-prefix[i-1]);
            }
        }
        //printf("\n");
        //for(int i=1;i<=n;i++) printf("%d-->\n",len[i]);
        //printf("\n\n");
        for(int i=0;i<=n;i++)//加上0~n个x后的最大值
        {
            int maxx=-0x3f3f3f3f;
            for(int k=1;k<=n;k++)
            {
                maxx=max(maxx,len[k]+min(k,i)*x);
            }
            printf("%d ",max(maxx,0));
        }
        printf("\n");
    }
    return 0;
}