309989: CF1768F. Wonderful Jump
Memory Limit：128 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Wonderful Jump
题意翻译
### 题目描述 给定整数 $n$ 和长度为 $n$ 的序列 $a$。 从位置 $i$ 跳到位置 $j(1\leq i\leq j\leq n)$ 需要花费 $\min(a_i,a_{i+1},\cdots,a_j)\times(j-i)^2$ 枚金币。 对于 $k=1,2,\cdots,n$，求出从位置 $1$ 经若干次跳跃后跳到位置 $k$ 需要的最小金币总数。 ### 输入格式 第一行输入一个整数 $n(2\leq n\leq4\times10^5)$。 接下来输入一行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\leq a_i\leq n)$。 ### 输出格式 输出一行 $n$ 个整数，其中第 $k$ 个整数表示从位置 $1$ 到位置 $k$ 所需的最小金币数。题目描述
You are given an array of positive integers $ a_1,a_2,\ldots,a_n $ of length $ n $ . In one operation you can jump from index $ i $ to index $ j $ ( $ 1 \le i \le j \le n $ ) by paying $ \min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2 $ eris. For all $ k $ from $ 1 $ to $ n $ , find the minimum number of eris needed to get from index $ 1 $ to index $ k $ .输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 2 \le n \le 4 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1,a_2,\ldots a_n $ ( $ 1 \le a_i \le n $ ).
输出格式
Output $ n $ integers — the $ k $ -th integer is the minimum number of eris needed to reach index $ k $ if you start from index $ 1 $ .
输入输出样例
输入样例 #1
3
2 1 3输出样例 #1
0 1 2输入样例 #2
6
1 4 1 6 3 2输出样例 #2
0 1 2 3 6 8输入样例 #3
2
1 2输出样例 #3
0 1输入样例 #4
4
1 4 4 4输出样例 #4
0 1 4 8说明
In the first example: - From $ 1 $ to $ 1 $ : the cost is $ 0 $ , - From $ 1 $ to $ 2 $ : $ 1 \rightarrow 2 $ — the cost is $ \min(2, 1) \cdot (2 - 1) ^ 2=1 $ , - From $ 1 $ to $ 3 $ : $ 1 \rightarrow 2 \rightarrow 3 $ — the cost is $ \min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2 $ . In the fourth example from $ 1 $ to $ 4 $ : $ 1 \rightarrow 3 \rightarrow 4 $ — the cost is $ \min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8 $ .Input
题意翻译
### 题目描述 给定整数 $n$ 和长度为 $n$ 的序列 $a$。 从位置 $i$ 跳到位置 $j(1\leq i\leq j\leq n)$ 需要花费 $\min(a_i,a_{i+1},\cdots,a_j)\times(j-i)^2$ 枚金币。 对于 $k=1,2,\cdots,n$，求出从位置 $1$ 经若干次跳跃后跳到位置 $k$ 需要的最小金币总数。 ### 输入格式 第一行输入一个整数 $n(2\leq n\leq4\times10^5)$。 接下来输入一行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\leq a_i\leq n)$。 ### 输出格式 输出一行 $n$ 个整数，其中第 $k$ 个整数表示从位置 $1$ 到位置 $k$ 所需的最小金币数。Output
**题目大意：**
给定一个长度为 $ n $ 的正整数数组 $ a_1, a_2, \ldots, a_n $。
你可以从索引 $ i $ 跳到索引 $ j (1 \le i \le j \le n) $，跳跃的花费是 $ \min(a_i, a_{i+1}, \ldots, a_j) \times (j - i)^2 $ 枚金币。
对于 $ k = 1, 2, \ldots, n $，计算从索引 $ 1 $ 开始，通过若干次跳跃到达索引 $ k $ 所需的最少金币数。
**输入格式：**
第一行包含一个整数 $ n (2 \le n \le 4 \times 10^5) $。
第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n (1 \le a_i \le n) $。
**输出格式：**
输出 $ n $ 个整数，第 $ k $ 个整数表示从索引 $ 1 $ 到索引 $ k $ 所需的最少金币数。
**输入输出样例：**
**输入样例 #1：**
```
3
2 1 3
```
**输出样例 #1：**
```
0 1 2
```
**输入样例 #2：**
```
6
1 4 1 6 3 2
```
**输出样例 #2：**
```
0 1 2 3 6 8
```
**输入样例 #3：**
```
2
1 2
```
**输出样例 #3：**
```
0 1
```
**输入样例 #4：**
```
4
1 4 4 4
```
**输出样例 #4：**
```
0 1 4 8
```
**说明：**
在第一个例子中：
- 从 $ 1 $ 到 $ 1 $：花费是 $ 0 $，
- 从 $ 1 $ 到 $ 2 $：$ 1 \rightarrow 2 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 = 1 $，
- 从 $ 1 $ 到 $ 3 $：$ 1 \rightarrow 2 \rightarrow 3 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 + \min(1, 3) \times (3 - 2)^2 = 1 + 1 = 2 $。
在第四个例子中，从 $ 1 $ 到 $ 4 $：$ 1 \rightarrow 3 \rightarrow 4 $ — 花费是 $ \min(1, 4, 4) \times (3 - 1)^2 + \min(4, 4) \times (4 - 3)^2 = 4 + 4 = 8 $。**题目大意：** 给定一个长度为 $ n $ 的正整数数组 $ a_1, a_2, \ldots, a_n $。 你可以从索引 $ i $ 跳到索引 $ j (1 \le i \le j \le n) $，跳跃的花费是 $ \min(a_i, a_{i+1}, \ldots, a_j) \times (j - i)^2 $ 枚金币。 对于 $ k = 1, 2, \ldots, n $，计算从索引 $ 1 $ 开始，通过若干次跳跃到达索引 $ k $ 所需的最少金币数。 **输入格式：** 第一行包含一个整数 $ n (2 \le n \le 4 \times 10^5) $。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n (1 \le a_i \le n) $。 **输出格式：** 输出 $ n $ 个整数，第 $ k $ 个整数表示从索引 $ 1 $ 到索引 $ k $ 所需的最少金币数。 **输入输出样例：** **输入样例 #1：** ``` 3 2 1 3 ``` **输出样例 #1：** ``` 0 1 2 ``` **输入样例 #2：** ``` 6 1 4 1 6 3 2 ``` **输出样例 #2：** ``` 0 1 2 3 6 8 ``` **输入样例 #3：** ``` 2 1 2 ``` **输出样例 #3：** ``` 0 1 ``` **输入样例 #4：** ``` 4 1 4 4 4 ``` **输出样例 #4：** ``` 0 1 4 8 ``` **说明：** 在第一个例子中： - 从 $ 1 $ 到 $ 1 $：花费是 $ 0 $， - 从 $ 1 $ 到 $ 2 $：$ 1 \rightarrow 2 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 = 1 $， - 从 $ 1 $ 到 $ 3 $：$ 1 \rightarrow 2 \rightarrow 3 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 + \min(1, 3) \times (3 - 2)^2 = 1 + 1 = 2 $。 在第四个例子中，从 $ 1 $ 到 $ 4 $：$ 1 \rightarrow 3 \rightarrow 4 $ — 花费是 $ \min(1, 4, 4) \times (3 - 1)^2 + \min(4, 4) \times (4 - 3)^2 = 4 + 4 = 8 $。
给定一个长度为 $ n $ 的正整数数组 $ a_1, a_2, \ldots, a_n $。
你可以从索引 $ i $ 跳到索引 $ j (1 \le i \le j \le n) $，跳跃的花费是 $ \min(a_i, a_{i+1}, \ldots, a_j) \times (j - i)^2 $ 枚金币。
对于 $ k = 1, 2, \ldots, n $，计算从索引 $ 1 $ 开始，通过若干次跳跃到达索引 $ k $ 所需的最少金币数。
**输入格式：**
第一行包含一个整数 $ n (2 \le n \le 4 \times 10^5) $。
第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n (1 \le a_i \le n) $。
**输出格式：**
输出 $ n $ 个整数，第 $ k $ 个整数表示从索引 $ 1 $ 到索引 $ k $ 所需的最少金币数。
**输入输出样例：**
**输入样例 #1：**
```
3
2 1 3
```
**输出样例 #1：**
```
0 1 2
```
**输入样例 #2：**
```
6
1 4 1 6 3 2
```
**输出样例 #2：**
```
0 1 2 3 6 8
```
**输入样例 #3：**
```
2
1 2
```
**输出样例 #3：**
```
0 1
```
**输入样例 #4：**
```
4
1 4 4 4
```
**输出样例 #4：**
```
0 1 4 8
```
**说明：**
在第一个例子中：
- 从 $ 1 $ 到 $ 1 $：花费是 $ 0 $，
- 从 $ 1 $ 到 $ 2 $：$ 1 \rightarrow 2 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 = 1 $，
- 从 $ 1 $ 到 $ 3 $：$ 1 \rightarrow 2 \rightarrow 3 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 + \min(1, 3) \times (3 - 2)^2 = 1 + 1 = 2 $。
在第四个例子中，从 $ 1 $ 到 $ 4 $：$ 1 \rightarrow 3 \rightarrow 4 $ — 花费是 $ \min(1, 4, 4) \times (3 - 1)^2 + \min(4, 4) \times (4 - 3)^2 = 4 + 4 = 8 $。**题目大意：** 给定一个长度为 $ n $ 的正整数数组 $ a_1, a_2, \ldots, a_n $。 你可以从索引 $ i $ 跳到索引 $ j (1 \le i \le j \le n) $，跳跃的花费是 $ \min(a_i, a_{i+1}, \ldots, a_j) \times (j - i)^2 $ 枚金币。 对于 $ k = 1, 2, \ldots, n $，计算从索引 $ 1 $ 开始，通过若干次跳跃到达索引 $ k $ 所需的最少金币数。 **输入格式：** 第一行包含一个整数 $ n (2 \le n \le 4 \times 10^5) $。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n (1 \le a_i \le n) $。 **输出格式：** 输出 $ n $ 个整数，第 $ k $ 个整数表示从索引 $ 1 $ 到索引 $ k $ 所需的最少金币数。 **输入输出样例：** **输入样例 #1：** ``` 3 2 1 3 ``` **输出样例 #1：** ``` 0 1 2 ``` **输入样例 #2：** ``` 6 1 4 1 6 3 2 ``` **输出样例 #2：** ``` 0 1 2 3 6 8 ``` **输入样例 #3：** ``` 2 1 2 ``` **输出样例 #3：** ``` 0 1 ``` **输入样例 #4：** ``` 4 1 4 4 4 ``` **输出样例 #4：** ``` 0 1 4 8 ``` **说明：** 在第一个例子中： - 从 $ 1 $ 到 $ 1 $：花费是 $ 0 $， - 从 $ 1 $ 到 $ 2 $：$ 1 \rightarrow 2 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 = 1 $， - 从 $ 1 $ 到 $ 3 $：$ 1 \rightarrow 2 \rightarrow 3 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 + \min(1, 3) \times (3 - 2)^2 = 1 + 1 = 2 $。 在第四个例子中，从 $ 1 $ 到 $ 4 $：$ 1 \rightarrow 3 \rightarrow 4 $ — 花费是 $ \min(1, 4, 4) \times (3 - 1)^2 + \min(4, 4) \times (4 - 3)^2 = 4 + 4 = 8 $。