AT_arc174_a [ARC174A] A Multiply 题解

题目翻译

给你一个长度为 \(N\) 的整数序列， \(A=(A_1,A_2,…,A_N)\) ，和一个整数 \(C\) 。

在执行以下操作最多一次后，找出A中元素的最大可能和:

选择两个整数 \(l\) 和 \(r\) （ \(1≤l≤r≤N\) ），

将 \(A_l,A_{l+1},…,A_r\) 分别乘以 \(C\) 。

算法

法一（暴力）

可以 \(O_{(N^2)}\) 暴力枚举 \(l\) 和 \(r\) 。

法二（正解）

前置知识：最大子段和。

参考该题思路，我们可以求出最大子段和，来最大化 \(C\) 乘上的区间和

代码如下：

#include<bits/stdc++.h>
#define int long long
#define fd(i,a,b) for(int i=a;i<=b;i=-~i)
using namespace std;
int n,c,a[300100],f[300100],sum[300100],maxx=-1e6,ans=0;
signed main()
{
	ios::sync_with_stdio(0);
	cin>>n>>c;
	fd(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i],maxx=max(a[i],maxx);
	//前缀和
	if(c>0&&maxx<0)//全负且c>0
	{
		cout<<sum[n];
		return 0;
	}
	if(c<=0)
	{
		fd(i,1,n) a[i]=-a[i];//将C<=0的情况转化为c>0的情况
	}
	fd(i,1,n)
	{
		if(i==1) f[i]=a[i];
		else f[i]=max(a[i],f[i-1]+a[i]);
		ans=max(ans,f[i]);
	}
	if(c>0) cout<<sum[n]+ans*(c-1);
	else cout<<sum[n]+ans*(1-c);
	//这里减一是因为sum[n]已经加过一次了
	return 0;
}

无关的话（审核大大，求过审）：被禁言了，怎么解啊？

感谢观看！