题面在这里&＃xff01;
好久没有体会这种A题的快感了23333
一开始看错了&＃xff0c;以为权值是从1开始的&＃xff0c;不过这样不要紧&＃xff0c;最后把算的答案减去两行数的和就是正确的答案了。
然后发现位于一个角上的时候&＃xff0c;我们其实只有两种选择&＃xff0c;一种是先一直走这一行走到头再返回来走&＃xff0c;这样就走完了&＃xff1b;另一种是走到这一列的另一行上然后再往右走一列。
第一种可以直接算&＃xff0c;第二种dp一下就好啦&＃xff0c;两种取一下最优。
#include
#define ll long long
using namespace std;
const int N&＃61;300005;inline int read(){int x&＃61;0; char ch&＃61;getchar();for(;!isdigit(ch);ch&＃61;getchar());for(;isdigit(ch);ch&＃61;getchar()) x&＃61;x*10&＃43;ch-&＃39;0&＃39;;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&＃43;1];}
inline ll getqz(int l,int r){ return qz[now][r]-qz[now][l-1];}int main(){n&＃61;read();for(int o&＃61;0;o<2;o&＃43;&＃43;){for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) a[o][i]&＃61;read(),qz[o][i]&＃61;qz[o][i-1]&＃43;(ll)a[o][i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) zq[o][i]&＃61;zq[o][i-1]&＃43;a[o][i]*(ll)i;for(int i&＃61;n;i;i--) fq[o][i]&＃61;fq[o][i&＃43;1]&＃43;a[o][i]*(ll)(n-i&＃43;1);}for(int i&＃61;n;i;i--)for(int o&＃61;0;o<2;o&＃43;&＃43;){now&＃61;o,f[o][i]&＃61;getzq(i,n)-getqz(i,n)*(ll)(i-1);now^&＃61;1,f[o][i]&＃43;&＃61;getfq(i,n)&＃43;getqz(i,n)*(ll)(n-i&＃43;1);ll tot&＃61;a[o][i]&＃43;2ll*a[o^1][i]&＃43;f[o^1][i&＃43;1];now&＃61;0,tot&＃43;&＃61;2ll*getqz(i&＃43;1,n),now&＃61;1,tot&＃43;&＃61;2ll*getqz(i&＃43;1,n);f[o][i]&＃61;max(f[o][i],tot);}now&＃61;0,f[0][1]-&＃61;getqz(1,n),now&＃61;1,f[0][1]-&＃61;getqz(1,n);printf("%I64d\n",f[0][1]);return 0;
}
京公网安备 11010802041100号