发布于2018年8月4日 由itewqq[CF][思维][预处理][枚举] CF1016C Vasya And The Mushrooms 这场CF也是崩了。。AB太慢而且wa了n发，C知道正确做法然后wa了3发剩20min放弃了。然后今天手算了五分钟ac emmmmm 这个要做到每个格子都只走一次，就必须先蛇形然后转圈，只不过中间从哪一点开始转圈决定了最后的答案大小。样例给的就是两种极端情况，一种是从一开始就开始转圈，另一种是一直蛇形直到最后。 预处理的话左边的从左往右推，右边的从右往左推，主要是右边的计算有点绕（其实也不是很绕主要是当时心态崩了emmm #include #include #include #include #include #include #include #include #include #include #include //#include using namespace std; typedef long long LL; const int maxn=1e6+5; const int MOD=1e9+7; LL board[2][maxn],dpl[maxn],dpr0[maxn],dpr1[maxn],sur[maxn]; int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int n; LL res=0; scanf("%d",&n); for (int i=0;i<2;i++) { for (int j=1;j<=n;j++) scanf("%d",&board[i][j]); } for (int i=n;i>0;i--) sur[i]+=sur[i+1]+board[0][i]+board[1][i]; for (int i=1;i<=n;i++) { if(i%2) dpl[i]=dpl[i-1]+2*(i-1)*board[0][i]+(2*i-1)*board[1][i]; else dpl[i]=dpl[i-1]+2*(i-1)*board[1][i]+(2*i-1)*board[0][i]; } for (int i=n;i>0;i--) { dpr0[i]=dpr0[i+1]-sur[i+1]+2*(i-1)*board[0][i]+(2*n-1)*board[1][i]; } for (int i=n;i>0;i--) { dpr1[i]=dpr1[i+1]-sur[i+1]+2*(i-1)*board[1][i]+(2*n-1)*board[0][i]; } for(int i=1;i<=n;i++) { if(i%2) res=max(dpr0[i]+dpl[i-1],res); else res=max(dpr1[i]+dpl[i-1],res); } cout<
