CF1644C Increase Subarray Sums

题目描述

You are given an array a_1, a_2, \dots, a_na1​,a2​,…,an​ , consisting of nn integers. You are also given an integer value xx .

Let f(k)f(k) be the maximum sum of a contiguous subarray of aa after applying the following operation: add xx to the elements on exactly kk distinct positions. An empty subarray should also be considered, it has sum 00 .

Note that the subarray doesn't have to include all of the increased elements.

Calculate the maximum value of f(k)f(k) for all kk from 00 to nn independently.

输入格式

The first line contains a single integer tt ( 1 \le t \le 50001≤t≤5000 ) — the number of testcases.

The first line of the testcase contains two integers nn and xx ( 1 \le n \le 50001≤n≤5000 ; 0 \le x \le 10^50≤x≤105 ) — the number of elements in the array and the value to add.

The second line contains nn integers a_1, a_2, \dots, a_na1​,a2​,…,an​ ( -10^5 \le a_i \le 10^5−105≤ai​≤105 ).

The sum of nn over all testcases doesn't exceed 50005000 .

输出格式

For each testcase, print n + 1n+1 integers — the maximum value of f(k)f(k) for all kk from 00 to nn independently.

题意翻译

题目简述

给定一个序列 \left\{a_n\right\}{an​} 与 整数 xx

定义 f(k)f(k) 表示经过如下操作后, 序列 aa 中最大的连续子段和: 将 aa 中 kk 个不同的位置上的数加上 xx

请求出 f(k),\ k\in[0, n]f(k), k∈[0,n]

输入数据

多组数据 TT (1\leq T\leq 50001≤T≤5000)

每组数据的第一行为 n, xn,x (1\leq n\leq 50001≤n≤5000, 0\leq x\leq 10^50≤x≤105)
第二行为 nn 个整数 a_1, a_2,\dots,a_na1​,a2​,…,an​, (-10^5\leq a_i\leq 10^5−105≤ai​≤105)

所有数据的 nn 的总和不超过 50005000

输入输出样例

输入 #1复制

3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4

输出 #1复制

10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8

说明/提示

In the first testcase, it doesn't matter which elements you add xx to. The subarray with the maximum sum will always be the entire array. If you increase kk elements by xx , k \cdot xk⋅x will be added to the sum.

In the second testcase:

• For k = 0k=0 , the empty subarray is the best option.
• For k = 1k=1 , it's optimal to increase the element at position 33 . The best sum becomes -1 + 5 = 4−1+5=4 for a subarray [3, 3][3,3] .
• For k = 2k=2 , it's optimal to increase the element at position 33 and any other element. The best sum is still 44 for a subarray [3, 3][3,3] .
• For k = 3k=3 , you have to increase all elements. The best sum becomes (-2 + 5) + (-7 + 5) + (-1 + 5) = 5(−2+5)+(−7+5)+(−1+5)=5 for a subarray [1, 3][1,3] .

 题意：让你求加上k个x之后子矩阵最大的和（k从0~n）

思路：先求每个长度子矩阵最大的和，len从1~n，当len==0的时候是空矩阵，就是0.

用f[i]来表示长度为i的子矩阵的最大和，因为ai有可能是负数，我们要找最大和，那么就把f初始化为-0x3f3f3f3f。

要很快的求子矩阵那么就需要找到他的前缀和。

求长度为len的子矩阵的时候，我们需要列举左端点从1~n，那么右端点就是i+len-1，这个以i为左端点长度为len的子矩阵的和就是s[i+len-1]-s[i-1]，然后我们列举左端点的时候取最大值就行，即

f[len]=max(f[len],s[i+len-1]-s[i-1])

操作是加上k个x。

当k<=len的时候，我们在f[len]里加上k个x就行

当k>len的时候，在这个区间里我们只能加len个x。

所以加的x的个数就是q=min(len,k)。

所以对于每个k，我们只需要列举len从1~n，取f[len]+x*q的最大值就行了。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
const int N=5005;
typedef long long ll;
ll n,x;
ll f[N],s[N],a[N];
void sove(){
	cin>>n>>x;
	memset(f,-0x3f,sizeof f);
	memset(s,0,sizeof s);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	for(int len=0;len<=n;len++){
		if(len==0)f[len]=0;
		else{
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
				f[len]=max(f[len],s[j]-s[i-1]);
			}
			
		}
	}
	for(int k=0;k<=n;k++){
		ll maxk=-0x3f3f3f3f;
		for(int len=0;len<=n;len++){
			ll q=min(k,len);
			maxk=max(maxk,f[len]+q*x);
		}
		cout<<maxk<<" ";
	}
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t;
	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}