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 $。
给定一个长度为 $ 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 $。