Four Segments CodeForces - 846C
2021/6/10 10:50:55
本文主要是介绍Four Segments CodeForces - 846C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
考察:枚举,前缀和
和本题的正解思路有点像的--->Go
题意:
在数组中放三个间断点,使得res最大.
思路:
三个间断点求最值,不能是在前缀区间只取正数,后缀区间只取负数,存在隔了负数出现大正数的情况.
可以枚举中间点mid,求[1,mid]的最大前缀,[mid,n]的最小后缀,两个for循环枚举时间复杂度O(N2)
Code
#include <iostream> #include <cstring> using namespace std; typedef long long LL; const int N = 5010; int n; LL sum[N]; void solve() { int pre = 0,mid,ed,sta; LL res = -1e14; for(int i=1;i<=n;i++)//枚举中间点,求前缀最大值 { if(sum[i]>sum[pre]) pre = i; LL temp = 2*sum[pre]-sum[i]; for(int j=i;j<=n;j++) {//(0~pre] (pre,i] (i,j] (j,n] LL t =temp+sum[j]-sum[i]-(sum[n]-sum[j]); if(t>res) { sta = pre; res = t; mid = i,ed = j; } } } printf("%d %d %d\n",sta,mid,ed); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); sum[i]=sum[i-1]+x; } solve(); return 0; }
这篇关于Four Segments CodeForces - 846C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享