CF1016C Vasya And The Mushrooms

题目：Vasya And The Mushrooms

题意：有一个人在 2 × n 的网格图上种蘑菇， (i, i) 位置的格子每单位时间会增长V(i,j)个蘑菇。他从 (1,1) 开始，每单位时间移动一个格子。他决定访问每个格子一次且仅一次。

思路：
依题意可得，轨迹一定如图所示：

（图丑求轻拍~）
那么就可以预处理出两段的和，在O（n）的时间内枚举分界线查询即可。

代码：

#include<bits/stdc++.h>
using namespace std;#define ll long long
#define maxn 300000int n;
ll a[3][maxn+5]= {
   0};
ll s[maxn+5];
ll sum[4][maxn+5];void readin() {scanf("%d",&n);for(int i=1; i<=2; i++) {for(int j=1; j<=n; j++) {scanf("%lld",&a[i][j]);}}
}void init() {for(int i=n; i>=1; i--) s[i]=s[i+1]+a[1][i]+a[2][i];int j=n;for(int i=n; i>=1; i--) {sum[1][i]=sum[1][i+1]+(i-1)*a[1][i]+j*a[2][i];j++;}j=n;for(int i=n; i>=2; i--) {sum[2][i]=sum[2][i+1]+i*a[2][i]+(j+1)*a[1][i];j++;}sum[2][1]=sum[2][2]+a[2][1];ll tot=0;for(int i=1; i<=n; i++) {sum[3][i]+=sum[3][i-1];if(i&1) {sum[3][i]+=tot*a[1][i]+(tot+1)*a[2][i];tot+=2;} else {sum[3][i]+=tot*a[2][i]+(tot+1)*a[1][i];tot+=2;}}
}ll slv() {ll ans=0;for(int i=0; i<=n; i++) {if(i&1) {ans=max(ans,sum[3][i]+sum[2][i+1]+(i-1)*s[i+1]);}else {ans=max(ans,sum[3][i]+sum[1][i+1]+i*s[i+1]);}}return ans;
}int main() {readin();init();ll ans=slv();printf("%lld",ans);return 0;
}