CodeForces - 1016C Vasya And The Mushrooms
2024-10-20 20:31:18
好久没有体会这种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;
}
最新文章
- 遍历Map的方法
- javasript_数据结构和算法_栈
- linux下安装nodejs
- HDU 1575
- SAP中数字计算时溢出捕获
- re模块(正则表达式)
- HDOJ 1590
- Java对象初始化详解
- 网络编程(发送get和post请求到服务器端,并获取响应)
- Android 访问权限设置记录-存档留着有用!
- N2N 对等VPN网络
- 完整的RecylerView的使用方法和例子
- 我的Python成长之路---第一天---Python基础(2)---2015年12月26日(雾霾)
- 扩展Python模块系列(二)----一个简单的例子
- SQLI DUMB SERIES-18
- C. Painting the Fence
- CVE-2011-0762环境搭建与EXP利用
- 第三节《Git重置》
- Linux&#160;目录结构学习与简析&#160;Part2
- python中requests已安装却仍报No module named requests错的原因
热门文章
- 避免无用的渲染绘制(Avoiding Unnecessary Paints)
- js_网页导出pdf文件
- 回溯算法_01背包问题_Java实现
- Thinkphp的SQL查询方式
- NoSQL-来自维基百科
- MySQL数据库的“十宗罪”【转】
- SQLserver连接本地服务器
- PHP laravel 5.0 Blade 模板引擎 Api使用备注
- 日志生成控制文件syslog.conf
- Codeforces 813B The Golden Age(数学+枚举)