CodeForces - 1016C Vasya And The Mushrooms

题面在这里！

好久没有体会这种A题的快感了23333

一开始看错了，以为权值是从1开始的，不过这样不要紧，最后把算的答案减去两行数的和就是正确的答案了。

然后发现位于一个角上的时候，我们其实只有两种选择，一种是先一直走这一行走到头再返回来走，这样就走完了；另一种是走到这一列的另一行上然后再往右走一列。

第一种可以直接算，第二种dp一下就好啦，两种取一下最优。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=300005;

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

int n,a[2][N],now;

ll f[2][N],qz[2][N],zq[2][N],fq[2][N];

inline ll getzq(int l,int r){ return zq[now][r]-zq[now][l-1];}

inline ll getfq(int l,int r){ return fq[now][l]-fq[now][r+1];}

inline ll getqz(int l,int r){ return qz[now][r]-qz[now][l-1];}

int main(){

	n=read();

	for(int o=0;o<2;o++){

        for(int i=1;i<=n;i++) a[o][i]=read(),qz[o][i]=qz[o][i-1]+(ll)a[o][i];

        for(int i=1;i<=n;i++) zq[o][i]=zq[o][i-1]+a[o][i]*(ll)i;

        for(int i=n;i;i--) fq[o][i]=fq[o][i+1]+a[o][i]*(ll)(n-i+1);

	}

	for(int i=n;i;i--)

		for(int o=0;o<2;o++){

		    now=o,f[o][i]=getzq(i,n)-getqz(i,n)*(ll)(i-1);

		    now^=1,f[o][i]+=getfq(i,n)+getqz(i,n)*(ll)(n-i+1);

		    ll tot=a[o][i]+2ll*a[o^1][i]+f[o^1][i+1];

		    now=0,tot+=2ll*getqz(i+1,n),now=1,tot+=2ll*getqz(i+1,n);

		    f[o][i]=max(f[o][i],tot);

		}

	now=0,f[0][1]-=getqz(1,n),now=1,f[0][1]-=getqz(1,n);

	printf("%I64d\n",f[0][1]);

	return 0;

}