链接：http://codeforces.com/contest/1016/problem/C
思路：首先观察可知一共有n个终点，所以自然想到遍历一遍复杂度应该为O(n)，但是要求和，如果不加以处理必定会上升到O(n^2)的复杂度，考虑以下：sum123表示从左到右走到头所摘蘑菇总数，sun321表示从右到左所摘蘑菇总数，sum111表示这一段初始蘑菇总和。我们观察到，不管什么时候开始走sum123+sum321的情况(即一路走到头再从上面回来，中间不转弯)，都与原始求的sum123与sum321差一个常数*sum111，因为可把复杂度变为O(n)
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
long long sum123[2][300001],sum321[2][300001],sum111[2][300001];
int n;
int a[2][300001];
int main(){
scanf("%d",&n);
for(int i=0;i<2;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=0;i<2;i++){
for(int j=n-1;j>=0;j--){
sum123[i][j] = sum123[i][j+1] + j*1LL*a[i][j]; //从i,j一直走到右边端点所摘磨菇数总和
sum321[i][j] = sum321[i][j+1] + (n-j)*1LL*a[i][j];//从右端点走到i,j所摘磨菇数总和
sum111[i][j] = sum111[i][j+1] + a[i][j];//初始磨菇数总和
}
}
long long res = 0;
long long sum = 0;
for(int i=0,j=0;j<n;++j,i^=1){//学会位运算，k^=1表示：k为偶数k-=1，k为奇数k+=1
long long nres = sum; //用sum维护左端一直拐弯的蘑菇总和
nres+=sum123[i][j] +j*1LL*sum111[i][j];//补上一个常数(j+1)*sum111的蘑菇数量
nres+=sum321[i^1][j] + (j+n-1)*1LL*sum111[i^1][j];//补上一个常数(j+n)*sum111的蘑菇数量
res = max(res,nres);//更新总和
sum+=a[i][j]*1LL*(j+j);//更新维护的和
sum+=a[i^1][j]*1LL*(j+j+1);
}
printf("%I64d\n", res);
return 0;
}
