题目链接传送门

题意:

  n个学生站一行,老师给每个学生发至少一个糖

  相邻学生,a[i] > a[i-1] 的话,那么右边学生的糖一定要发得比左边学生的糖多

  问你满足条件这个老师总共最少的发多少糖

题解:

  向左向右连续递增的话发的糖数量就递增,否则就是1个

  取一个max即可

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 5e5+, M = 1e2+,inf = 2e9,mod = 1e9+; int a[N],n,dp1[N],dp2[N];
int main() {
scanf("%d",&n);
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
for(int i = ; i <= n; ++i) {
dp1[i] = ;
dp2[i] = ;
}
for(int i = ; i <= n; ++i) {
if(a[i] > a[i-]) dp1[i] = dp1[i-] + ;
}
for(int i = n-; i >= ; --i) {
if(a[i+] < a[i]) dp2[i] = dp2[i+] + ;
}
LL ans = ;
for(int i = ; i <= n; ++i) ans += max(dp1[i],dp2[i]);
cout<<ans<<endl;
return ;
}

最新文章

  1. json中含有Unicode的处理办法 C#
  2. jq pagination分页 全选、单选的思考
  3. Git代码管理常用命令
  4. Tkprof工具详解一
  5. Sprint1(11.20)
  6. 本地预览图片html和js例子
  7. 检查c# 内存泄漏
  8. C与C++存储空间布局
  9. iPhone/iPad全屏截图与区域截图的几种方法
  10. sed使用范例
  11. opacity设定图片透明度
  12. java.lang.IllegalStateException: Zip File is closed
  13. Spring boot&amp;Mybatis 启动报错 Failed to auto-configure a DataSource
  14. web项目中配置文件的加载顺序
  15. 设置将Maven的jar包发布到lib
  16. PostgreSQL操作数据表
  17. dorado重置按钮事件
  18. UVA-12661 Funny Car Racing (dijkstra)
  19. [转]VS2010中使用模块定义文件(.def)
  20. java音频播放器

热门文章

  1. OAuth2.0授权流程
  2. Python之微信-微信好友头像合成
  3. 剑指Offer(书):删除链表的节点
  4. php添加了环境变更,还是显示 不是内部或外部命令 (注:添加到目录即可,不加 php.exe )
  5. 【06】sass编译工具(弃)
  6. 【Codeforces 1083A】The Fair Nut and the Best Path
  7. STM32F407 NVIC 中断优先级管理 个人笔记
  8. 二分图最大权完美匹配KM算法
  9. CodeVs1519 过路费
  10. 【cmd】cmd常用命令