CF1946B Maximum Sum 题解

题目简述

你有一个由 $n$ 个整数组成的数组 $a$。

你要对它进行 $k$ 次操作。在一次操作中，你选择了数组 $a$ 的任意连续子数组（可能为空），并在数组的任意位置插入了该子数组的和。

你的任务是找出经过 $k$ 次操作后数组的最大和。

题目分析

这道题显然是一道贪心题。

对于第 $1$ 次操作，选择的话肯定是选最大的好，所以我们会找出原序列的最大子段和进行插入，为了使下一次的插入子段更大，所以我们一定会插入原序列的最大子段和中。进行 $m$ 次操作，执行 $m$ 次上述操作即可。

直接模拟的话肯定不行，我们考虑找找规律，由于每次插入都是插入现在序列的最大子段和中，所以每次插入的值都是翻倍增长的，易发现这是一个等比数列的求和。我们如果模拟上述操作，复杂度为 $\mathcal{O}(m)$，可以接受。

最后注意取模。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10,mod=1e9+7;
int n,k,a[N],T;
ll Max,f,sum,mul;
void solve()
{
	cin>>n>>k;
	Max=f=sum=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f=max(a[i]*1ll,a[i]+f);
		Max=max(f,Max);
		sum+=a[i];
	}
	Max%=mod;
	sum=(sum%mod+mod)%mod;
	mul=1;
	for(int i=1;i<=k;i++)
	{
		sum=(sum+mul*Max%mod+mod)%mod;
		mul=mul*2%mod;
	}
	cout<<sum<<"\n";
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
    	solve();
	}
	return 0;
}