P3918

题目

题目描述：

神犇航空开展了一项载客特技飞行业务。每次飞行长 nn 个单位时间，每个单位时间可以进行一项特技动作，可选的动作有 kk 种，每种动作有一个刺激程度 cic_i。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间) ，若为第一次进行该动作，价值为 00。安排一种方案，使得总价值最大。

输入格式：

第一行，两个整数，nn 和 kk，如上所述；

第二行，kk 个整数，表示 kk 种动作的 cic_i 值。

输出格式：

仅一行，一个整数，表示最大总价值。

数据范围与说明：

数据规模与约定

  • 对于 10%10\% 的测试数据，n≤20n \le 20，k≤3k \le 3。
  • 对于 100%100\% 的测试数据，1≤n≤1031 \le n \le 10^3，1≤k≤3001 \le k \le 300，0≤ci≤1030 \le c_i \le 10^3。

输入输出样例 #1

输入：

1
2
5 2
2 2

输出：

1
12

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> c(k);
    for (int i = 0; i < k; i++) {
        cin >> c[i];
    }
    sort(c.begin(), c.end(), greater<int>());
    int left = 0, right = n - 1;
    int ans = 0;
    for (int i = 0; i < k; i++) {
        if (left > right) break;
        ans += (right - left) * c[i];
        left++;
        right--;
    }
    cout << ans << endl;
    return 0;
}