Toggle navigation
ZUAOJ
常见问答
问题
状态
排名
竞赛&作业
[
问题
状态
排名
统计
]
Login
问题 o: 小H分糖果(动态规划)
问题 o: 小H分糖果(动态规划)
时间限制:
1 Sec
内存限制:
128 MB
提交:
1582
解决:
1160
[
提交
][
状态
][
讨论版
][命题人:
]
题目描述
小H来到一个小学分糖果,小学生们很听话,站成一排等着分糖果,小H将根据每个人的上次考试分数给一定的糖果,规则如下。
每个人都有自己分数
a
i
,代表上次考试成绩。
每个人都至少有一颗糖。
如果两个人相邻,分数高的一定比分数低的糖果多
然而小H经费有限,他想知道最少需要多少糖果。
输入
输入第一行包括一个整数
n(1≤n≤10
5
)
。 接下来n行,每行1个整数
ai(1≤a
i
≤10
5
)
表示站在第
i
位的人的分数。
输出
输出最少需要多少糖果
样例输入
3 1 2 2
样例输出
4
提示
[
提交
][
状态
]