题解 CF33C 【Wonderful Randomized Sum】

2018-06-29 10:12:28


利用数学推导,排除无关变量,然后进行求解。


应该可以看出,前缀和后缀交叉的情况下,交叉的那部分,相当于没有变化。 那么

据题可知:

设 前缀为A,后缀为B,未变化部分的为C。序列数字总和为S(允许A,B,C都为空的情况,此时A=B=C=0)

因为 A+B+C=S,需求解为 -(A+B)+C 的最大值

所以 —(A+B)+C的最大值 = —(S-C)+C的最大值 = 2C-S


综上 显然S是定值,我们要做的就是让C最大,问题就变成了求最大子段和了。

LuckyCloud 

附上丑陋的代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,Max,S,a[100093],sum,ans;
inline long long read()
{
  long long cnt=0,f=1;char ch=getchar();
  while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
  while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
  return cnt*f;
}
int main()
{
  n=read();
  for (int i=1;i<=n;i++)
  {
   a[i]=read();
   sum+=a[i];
  }
  for (int i=1;i<=n;i++)
   if (S+a[i]<0) S=0;
   else {S+=a[i];Max=max(Max,S);}
  Max=max(Max,S);
  ans=Max*2-sum;
  printf("%lld\n",ans);
  return 0;
}