309793: CF1736E. Swap and Take

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Swap and Take

题意翻译

给定一个长为 $n$ 的正整数序列 $a$。初始你的分数为 $0$,需要进行 $n$ 轮操作。 在第 $i$ 轮,你可以选择交换两个相邻的数并将其中一个变为 $0$,也可以啥都不干。无论是否交换,第 $i$ 轮结束后你的分数会多 $a_i$。 求你最大能得到的分数。

题目描述

You're given an array consisting of $ n $ integers. You have to perform $ n $ turns. Initially your score is $ 0 $ . On the $ i $ -th turn, you are allowed to leave the array as it is or swap any one pair of $ 2 $ adjacent elements in the array and change exactly one of them to $ 0 $ (and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add $ a_i $ to your score. What's the maximum possible score you can get?

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 2 \le n \le 500 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ ).

输出格式


Print a single integer — the maximum possible score.

输入输出样例

输入样例 #1

2
3 1

输出样例 #1

6

输入样例 #2

5
7 3 9 6 12

输出样例 #2

52

说明

In the first example, to get the maximum score we do as follows. Do nothing on the first turn, add $ 3 $ to the score. Swap the first and the second elements and turn $ 1 $ to $ 0 $ on the second turn, and add $ 3 $ to the score. The final score is $ 6 $ .

Input

题意翻译

给定一个长为 $n$ 的正整数序列 $a$。初始你的分数为 $0$,需要进行 $n$ 轮操作。 在第 $i$ 轮,你可以选择交换两个相邻的数并将其中一个变为 $0$,也可以啥都不干。无论是否交换,第 $i$ 轮结束后你的分数会多 $a_i$。 求你最大能得到的分数。

Output

**题意翻译**

给定一个长度为 $ n $ 的正整数序列 $ a $。最初你的分数为 $ 0 $,需要进行 $ n $ 轮操作。

在第 $ i $ 轮,你可以选择交换两个相邻的数并将其中一个变为 $ 0 $,也可以什么都不做。无论是否交换,第 $ i $ 轮结束后你的分数会增加 $ a_i $。

求你最大能得到的分数。

**题目描述**

你给定一个包含 $ n $ 个整数的数组。你必须执行 $ n $ 个回合。

最初你的分数是 $ 0 $。

在第 $ i $ 回合,你可以选择保持数组不变,或者交换数组中任意一对相邻的元素,并在交换后改变其中恰好一个元素为 $ 0 $(另一个元素保持不变)。在任何情况下(无论你是否交换),之后你将 $ a_i $ 加到你的分数上。

你能得到的最大可能分数是多少?

**输入输出格式**

**输入格式**

第一行包含一个整数 $ n $ ( $ 2 \le n \le 500 $ )。

第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ )。

**输出格式**

打印一个整数——可能得到的最大分数。

**输入输出样例**

**输入样例 #1**

```
2
3 1
```

**输出样例 #1**

```
6
```

**输入样例 #2**

```
5
7 3 9 6 12
```

**输出样例 #2**

```
52
```

**说明**

在第一个例子中,为了得到最大分数,我们这样做。第一回合什么都不做,分数加上 $ 3 $。第二回合交换第一个和第二个元素,并将第一个元素变为 $ 0 $,分数再加上 $ 3 $。最终分数是 $ 6 $。**题意翻译** 给定一个长度为 $ n $ 的正整数序列 $ a $。最初你的分数为 $ 0 $,需要进行 $ n $ 轮操作。 在第 $ i $ 轮,你可以选择交换两个相邻的数并将其中一个变为 $ 0 $,也可以什么都不做。无论是否交换,第 $ i $ 轮结束后你的分数会增加 $ a_i $。 求你最大能得到的分数。 **题目描述** 你给定一个包含 $ n $ 个整数的数组。你必须执行 $ n $ 个回合。 最初你的分数是 $ 0 $。 在第 $ i $ 回合,你可以选择保持数组不变,或者交换数组中任意一对相邻的元素,并在交换后改变其中恰好一个元素为 $ 0 $(另一个元素保持不变)。在任何情况下(无论你是否交换),之后你将 $ a_i $ 加到你的分数上。 你能得到的最大可能分数是多少? **输入输出格式** **输入格式** 第一行包含一个整数 $ n $ ( $ 2 \le n \le 500 $ )。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ )。 **输出格式** 打印一个整数——可能得到的最大分数。 **输入输出样例** **输入样例 #1** ``` 2 3 1 ``` **输出样例 #1** ``` 6 ``` **输入样例 #2** ``` 5 7 3 9 6 12 ``` **输出样例 #2** ``` 52 ``` **说明** 在第一个例子中,为了得到最大分数,我们这样做。第一回合什么都不做,分数加上 $ 3 $。第二回合交换第一个和第二个元素,并将第一个元素变为 $ 0 $,分数再加上 $ 3 $。最终分数是 $ 6 $。

加入题单

上一题 下一题 算法标签: