CF1667A.Make it Increasing

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given an array $a$ consisting of $n$ positive integers, and an array $b$ , with length $n$ . Initially $b_i=0$ for each $1 \leq i \leq n$ .

In one move you can choose an integer $i$ ( $1 \leq i \leq n$ ), and add $a_i$ to $b_i$ or subtract $a_i$ from $b_i$ . What is the minimum number of moves needed to make $b$ increasing (that is, every element is strictly greater than every element before it)?

输入格式

The first line contains a single integer $n$ ( $2 \leq n \leq 5000$ ).

The second line contains $n$ integers, $a_1$ , $a_2$ , ..., $a_n$ ( $1 \leq a_i \leq 10^9$ ) — the elements of the array $a$ .

输出格式

Print a single integer, the minimum number of moves to make $b$ increasing.

输入输出样例

输入#1
```
5
1 2 3 4 5
```
输出#1
```
4
```
输入#2
```
7
1 2 1 2 1 2 1
```
输出#2
```
10
```
输入#3
```
8
1 8 2 7 3 6 4 5
```
输出#3
```
16
```

说明/提示

Example $1$ : you can subtract $a_1$ from $b_1$ , and add $a_3$ , $a_4$ , and $a_5$ to $b_3$ , $b_4$ , and $b_5$ respectively. The final array will be [ $-1$ , $0$ , $3$ , $4$ , $5$ ] after $4$ moves.

Example $2$ : you can reach [ $-3$ , $-2$ , $-1$ , $0$ , $1$ , $2$ , $3$ ] in $10$ moves.

首页