Make it Increasing

题面翻译

题目描述

给定一个包含 $n$ 个正整数的数列 $a$ 以及一个长度为 $n$ 的数列 $b$ ,初始时数列 $b$ 的每一个元素都为0。定义一次操作为把数列 $b$ 中的某个元素 $b_i$ 加上或减去 $a_i$ 的值，求使得数列 $b$ 严格递增最小的操作次数。

输入格式

第一行为一个整数 $n$ $(2 \le n \le 5000)$，第二行为 $n$ 个正整数，$a_1$ , $a_2$ , ... , $a_n$ $(1 \le a_i \le {10}^9)$ ，作为数列 $a$ 的值。

输出格式

输出使数列 $b$ 严格递增的最小操作次数。

题目描述

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

样例输入 #1

5
1 2 3 4 5

样例输出 #1

4

样例 #2

样例输入 #2

7
1 2 1 2 1 2 1

样例输出 #2

10

样例 #3

样例输入 #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.