CodeForces-1016C Vasya And The Mushrooms(模拟+思维+前缀和的前缀和) 解题报告 Apare_xzc

CodeForces-1016C Vasya And The Mushrooms(模拟+思维+二重前缀和 ) 解题报告

xzc 2019/4/7

这周周赛的C题：wyt学姐的恶意
  这道题周赛的时候就出思路了，但是觉得可能很不好写，20分钟写了个大概，处理了前缀后缀和以及二重前缀后缀和，没推完公式

vjudge链接
codeforces链接

题意：

  有一个蘑菇园，是一个2*n的方格地。每个格子里都有一颗蘑菇，蘑菇的生长速度不同。
  Vasya这个人一开始站在左上角那个格子里，他必须走到每个格子里去采蘑菇，并且不能停留，1秒移动到一个相邻的格子，并且迅速采了这个格子的蘑菇(时间忽略不计)，然后马上离开。而且他必须经过每个格子1次。
  一开始时间为蘑菇高度都为0。求这个人能采到蘑菇高度之和的最大值是多少。(左上角那株肯定是0)

输入：

  n
  a1 a2 … an(代表第一行每列蘑菇每秒生长的高度)
  b1 b2 … bn(代表第二行每列蘑菇每秒生长的高度)

输出：

  一个整数，表示他能采到蘑菇高度之歌的最大值

Sample

 input1

3
1 2 3
6 5 4

 output1

70

 input2

3
1 1000 10000
10 100 100000

 output2

543210

input3(不用谢我)

6
12 8 12 17 20 5
17 4 8 8 8 4

output3

705

input4(不用谢我)

6
16 20 18 7 14 2
17 12 4 10 7 4

output4

741

分析：

（以样例4为例）

我们可以把每个位置用一个字母标号：

• 那么，根据题意，这个人一开始在A这里，他必须采了高度为0的蘑菇，然后马上向相邻的格子转移，他只能向下走或者向右走。
• 那么，根据题目的要求，他每个格子只能走一次，如果他第一步向右边走到了B,那么他的路径就确定了，只能是A->B->C->D->E->F->L->K->J->I->H->G
• 如果他第一步往下走，到了G,那么他下一步只能往右从G到H
• 现在他到了H，他又有2种选择：向右走到I(A->G->H->I),或者向上走到B(A->G->H->B)
• 如果他选的是从H到I,那么他的路径又确定了，只能是A->G->H->I->J->K->L->F->E->D->C->B
• 如果他选的是从H到B,那么他下一步只能往右从B到C
• 现在他到了C，他又有两种选择：向右走到D(A->G->H->B->C->D),或者向下走到I(A->G->H->B->C->I)
• 如果他选的是从C到D,那么他他的路径叒确定了，只能是A->G->H->B->C->D->E->F->L->K->J->I
• 如果他选的是从C到I,那么下一步他只能往右到J,继续走蛇形…
• (你懂我意思了吧)

所以，我们的思路就确定了，他能走的路线不多，少于2*n条，所以，我们可以用每条路线的答案ans去更新最终的结果res
我们可以这样写：
  循环的主线是让他走蛇形A->G->H->B->C->I->J->D->E->K->L->F
  在走这条主线的时候，在每个位置，如果该上下了他却往右走了，那么他的路径就确定了，我们计算一下他开小差走的其它路径的答案，更新一下结果，然后继续走蛇形
  那么问题来了，循环主线复杂度是O(2*n)的，我们能否O(1)或者O(logn)地求出图中每个点“开小差”后的结果呢？
我们就想到了前缀和

我们来模拟一下某一条路：
假如我们走蛇形，走到第4列J的位置，此时的时间t=7，我们本应该向上走到D,但是我们从J向右走到了K,那么后面的路就是(A->G->H->B->C->I->J)->K->L->F->E->D
那么我们如何计算从K到D这一段蘑菇的高度(设为h)呢？
我们可以暴力地算一遍:
h = 8*K + 9*L + 10*F + 11*E + 12*D
那么，我们可以先从J和L开始计时,把h表示为：
h = (1+7)*K + (2+7)*L + (1+9)*E + (2+9)*D

那么，7和9是怎么来的呢？
设J所在列数为i，则i = 4
7 = t
10 = 7+6-4 = t+n-i
那么h就可以表示为:

  t * (b[i]+b[i+1]+...+b[n])  -------------------->(1)
+ b[i]*1 + b[i+1]*2 + ... + b[n]*(n-i+1) --------->(2)    
+ (t+n-i) * (a[n]+a[n-1]+a[n-1]+...+a[i])--------->(3) 
+ a[n]*1 + a[n-1]*2 + ... + a[i]*(n+1-i) --------->(4)

那我们要如何求这4个式子呢？

• 显然(1)(3)可以用数组a,b的前缀和(后缀和更好)
• 那么(2)(4)怎么求呢？
• 注意了！(2)不就是数组b<mark>后缀和的后缀和</mark>吗？
      (4)不就是数组a<mark>前缀和的前缀和</mark>吗？

我们可以预处理之后O(1)算出来(1)(2)(3)(4)

至此，这题可以做了，而且复杂度为O(n)
我们先定义几个数组
sumaL: a数组的前缀和
sumaR: a数组的后缀和
sal : a数组前缀和的前缀和
sar : a输入后缀和的后缀和
(b的同理)

上代码：

/* Author: XuZhichao Status: Accepted Time: 124ms Memory: 23512kB Length: 1864 Lang: GNU G++11 5.1.0 Submitted: 2019-04-07 00:53:49 */
#include <bits/stdc++.h>
#define Mst(a,b) memset(a,(b),sizeof(a))
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 3e5 + 100;
LL a[maxn],b[maxn],res; 
LL sumaL[maxn],sumaR[maxn],sumbL[maxn],sumbR[maxn];
LL sal[maxn],sar[maxn],sbl[maxn],sbr[maxn];
void downToRight(LL ans,int i,int n,LL t)
{
	ans += t*sumbR[i+1]+sbr[i+1]+(t+n-i)*sumaR[i]-sal[i-1]+sal[n]-sumaL[i-1]*(n-i+1);
	res = max(res,ans);
}
void upToRight(LL ans,int i,int n,LL t)
{
	ans += t*sumaR[i+1]+sar[i+1]+(t+n-i)*sumbR[i]-sbl[i-1]+sbl[n]-sumbL[i-1]*(n-i+1);
	res = max(res,ans);
}
int main()
{
	//freopen("in.txt","r",stdin);
	int n;
	int ca = 0;
	while(scanf("%d",&n)!=EOF)
	{
		if(ca++)
		{
			sumaL[0] = sumaL[n+1] = 0;
			sumbL[0] = sumbL[n+1] = 0;
			sumaR[0] = sumaR[n+1] = 0;
			sumbL[0] = sumbR[n+1] = 0;
			sal[0] = sal[n+1] = 0;
			sar[0] = sar[n+1] = 0;
			sbl[0] = sbl[n+1] = 0;
			sbr[0] = sbr[n+1] = 0;
		}
		For(i,1,n) scanf("%lld",a+i),sumaL[i] = sumaL[i-1]+a[i];
		For(i,1,n) scanf("%lld",b+i),sumbL[i] = sumbL[i-1]+b[i];
		if(n==1)
		{
			printf("%lld\n",b[1]);
			continue;
		}
		Rep(i,n,1) sumaR[i] = sumaR[i+1]+a[i],sumbR[i] = sumbR[i+1]+b[i];
		For(i,1,n) sal[i]  = sal[i-1]+sumaL[i], sbl[i] = sbl[i-1]+sumbL[i];
		Rep(i,n,0) sar[i]  = sar[i+1]+sumaR[i], sbr[i] = sbr[i+1]+sumbR[i];
		res = 0;
		res = sar[2]+sbl[n]+sumbL[n]*(n-1);
		LL t = 0;
		LL ans = 0;
		For(i,1,n)  
		{
			++t;
			if(i&1) ans += t*b[i];
			else ans += t*a[i];
			if(i==n) 
			{
				res = max(res,ans);
				continue;
			}
			++t;
			if(i&1)
			{
				ans += t*b[i+1];
				if(i<n-1)
					downToRight(ans,i+1,n,t); 
			}
			else
			{
				ans += t*a[i+1];
				if(i<n-1)
					upToRight(ans,i+1,n,t);
			}
		}
		printf("%lld\n",res);
	}
	
	return 0;
}