题面在这里!

好久没有体会这种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;
}

  

最新文章

  1. 遍历Map的方法
  2. javasript_数据结构和算法_栈
  3. linux下安装nodejs
  4. HDU 1575
  5. SAP中数字计算时溢出捕获
  6. re模块(正则表达式)
  7. HDOJ 1590
  8. Java对象初始化详解
  9. 网络编程(发送get和post请求到服务器端,并获取响应)
  10. Android 访问权限设置记录-存档留着有用!
  11. N2N 对等VPN网络
  12. 完整的RecylerView的使用方法和例子
  13. 我的Python成长之路---第一天---Python基础(2)---2015年12月26日(雾霾)
  14. 扩展Python模块系列(二)----一个简单的例子
  15. SQLI DUMB SERIES-18
  16. C. Painting the Fence
  17. CVE-2011-0762环境搭建与EXP利用
  18. 第三节《Git重置》
  19. Linux&#160;目录结构学习与简析&#160;Part2
  20. python中requests已安装却仍报No module named requests错的原因

热门文章

  1. 避免无用的渲染绘制(Avoiding Unnecessary Paints)
  2. js_网页导出pdf文件
  3. 回溯算法_01背包问题_Java实现
  4. Thinkphp的SQL查询方式
  5. NoSQL-来自维基百科
  6. MySQL数据库的“十宗罪”【转】
  7. SQLserver连接本地服务器
  8. PHP laravel 5.0 Blade 模板引擎 Api使用备注
  9. 日志生成控制文件syslog.conf
  10. Codeforces 813B The Golden Age(数学+枚举)