线性dp,后缀处理——cf1016C好题
2024-10-07 21:15:34
绝对是好题
#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define ll long long
ll sum1[maxn],sum2[maxn],sum3[maxn],sum[maxn],n,a[maxn][];
int main(){
cin>>n;
for(int i=;i<=n;i++)cin>>a[i][];
for(int i=;i<=n;i++)cin>>a[i][];
for(int i=;i<=n;i++){//形状1的长度
if(i%==){
sum3[i]=sum3[i-];
sum3[i]+=a[i][]*(*i-);
sum3[i]+=a[i][]*(*i-);
}
else {
sum3[i]=sum3[i-];
sum3[i]+=a[i][]*(*i-);
sum3[i]+=a[i][]*(*i-);
}
}
for(int i=n;i>=;i--)//求一下后缀
sum[i]=sum[i+]+a[i][]+a[i][]; for(int i=n;i>=;i--){//上面往下绕的权值
sum1[i]+=(*n-)*a[i][];//下面的贡献是2*n-1
sum1[i]+=*(i-)*a[i][];//下面的贡献是2*(i-1)
sum1[i]+=sum1[i+]-sum[i+];
}
for(int i=n;i>=;i--){//下面往上绕的权值
sum2[i]+=*(i-)*a[i][];//下面的贡献是2*(i-1)
sum2[i]+=(*n-)*a[i][];
sum2[i]+=sum2[i+]-sum[i+];
}
ll ans=;
for(int i=;i<=n;i++) {
if(i%==)ans=max(ans,sum3[i]+sum1[i+]);
else ans=max(ans,sum3[i]+sum2[i+]);
}
cout<<ans<<endl;
}
最新文章
- 第三方提权之serv-u提权
- 页面以base64输出图片
- Mac系统下显示和隐藏文件
- ABAP 数值类型转换
- 查询反模式 - GroupBy、HAVING的理解
- 所有Mac用户都需要知道的9个实用终端命令行
- 61. 从1到n,共有n个数字,每个数字只出现一次。从中随机拿走一个数字x,请给出最快的方法,找到这个数字。如果随机拿走k(k>;=2)个数字呢?[find k missing numbers from 1 to n]
- js 获取cookie
- spring事务注解
- json 转 javaBean
- python 以标准输出(sys.stdout)为例,看python的标准输入、标准错误输出
- zabbix client安装配置执行
- Codeforces Round #193 (Div. 2)
- CodeForces 722B
- Weex系列二、显示图片
- 【BZOJ1901】【Luogu2617】Dynamic Ranking(主席树,树状数组)
- centos7 修改ip和dns
- 各个模式的accesstoken续期详解
- 分布式版本控制系统GIT的使用
- 2017-6-6&;6-8/大型网站架构总结