[Luogu2422]良好的感觉
题目描述
kkk做了一个人体感觉分析器。每一天,人都有一个感受值Ai,Ai越大,表示人感觉越舒适。在一段时间[i, j]内,人的舒适程度定义为[i, j]中最不舒服的那一天的感受值 * [i, j]中每一天感受值的和。现在给出kkk在连续N天中的感受值,请问,在哪一段时间,kkk感觉最舒适?
输入输出格式
输入格式:
第一行为N,代表数据记录的天数
第二行N个整数,代表每一天的感受值
输出格式:
一行,表示在最舒适的一段时间中的感受值。
输入输出样例
6
3 1 6 4 5 2
60
说明
样例解释:
kkk最开心的一段时间是第3天到第5天,开心值:(6+4+5)*4=60
对于30%的数据,1<=N<=100
对于70%的数据,1<=N<=2000
对于100%的数据,1<=N<=100000,1<=感受值<=1000000
一看貌似就是单调队列优化DP...
然后越看越不像...
我们想一下暴力怎么写,枚举一个点i,值为x,找到左边第一个小于x的位置记为l, 同样的找到右边第一个小于x的位置记作r。
于是显然我们的答案就是x*(qzh[r]-qzh[l-1]),qzh指前缀和数组。这样显然是O(n^2)的,我们考虑优化。
因为题目的特性,很容易想到用单调栈维护递增序列。
我们用单调栈存储下标,保证下标对应的值是单调递增的。
于是我们对于一个新位置i,它的值为x,然后弹掉栈顶值比x大的,直到val[stack[top]] < x。
我们把弹出的那些下标的右端点(即右边第一个比它的值小的位置)设为i。
然后对于新插入的i,我们把i的左端点(与上面类似)设为top-1。
考虑这个做法的正确性。
我们的栈里的坐标是单调递增的,值也是单调递增的,我们新插入的值也如果比前面的小,一定是第一个比前面小的数(显然)。
我们弹晚之后剩下的最后一个一定是坐标最大的比x小的数。
所以我们处理完以上之后再O(n)统计一下答案就行了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read(){
int res=;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){res=(res<<)+(res<<)+(ch^);ch=getchar();}
return res;
}
#define ll long long int n;
int a[];
ll qzh[];
ll stack[], top; //维护下标
int le[], ri[];
ll ans; int main()
{
n = read();
for (int i = ; i <= n ; i ++) a[i] = read(), qzh[i] = qzh[i-] + a[i];
for (int i = ; i <= n ; i ++)
{
while(top and a[stack[top]] >= a[i]) ri[stack[top--]] = i;
le[i] = stack[top];
stack[++top] = i;
}
for (int i = ; i <= n ; i ++) {if (!le[i]) le[i] = ;if (!ri[i]) ri[i] = n;}
for (int i = ; i <= n ; i ++) ans = max(ans, a[i] * (qzh[ri[i]-] - qzh[le[i]]));
printf("%lld\n", ans);
return ;
}
最新文章
- DevExpress控件的GridControl控件小结
- Eclipse创建maven项目
- 正确运用synchronized和二次判断 实现多线程安全
- CreateDIBSection函数
- 使用Apache HttpClient
- 这个好像、也许、或许、大概、应该、Maybe真的可以算是传说中的Spring.Net了吧
- ASP.net 判断上传文件类型的三种方法
- PJSIP在windows(xp或者win7)下的编译,编译工具是vs2008,PJSIP版本2.3
- winform —— 界面
- log4j配置示例
- jquery mobile多页面跳转等,data-ajax=";false"; 问题,
- 2017-2-28 C#基础 数组
- 方伯伯的玉米田[SCOI2014]
- 膜拜rqy
- EntityFramework使用总结(与MVC4.0实现CURD操作)
- SpringMvc执行过程
- django xadmin 安装和使用
- HDU 1106 排序 (排序+处理字符串)
- make linux test main attempt to index a nil value
- Asp.Net MVC +EF CodeFirst+多层程序设计
热门文章
- MapReduce原理及操作
- FJUT - OJ优先队列专题题解
- charles Web界面设置
- JavaScript之深入对象(一)
- java.sql.SQLException: Data truncation: Incorrect string value: &#39;\xE5\x91\xA8\xE6\x9D\xBE&#39; for column &#39;cname&#39; at row 1 Query
- 2019年9月末周java面试总结
- Android Adapter的一些记录
- 讨论c/c++计算小数的精度问题
- springboot 集成Redis单机
- 给定一个公式字符串用java进行拆解并计算结果