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