题意

\(k(1 \le k \le 300)\)种物品，价值分别为\(c_i(0 \le c_i \le 1000)\)。有\(n(1 \le n \le 1000)\)分钟，每分钟可以选择一个物品\(i\)，价值为距离上次选择该物品的时间 * \(c_i\)。求最大价值。

分析

发现对于一种物品，价值为\(c_i * \sum_{j=2}^{a} (t_j-t_{j-1}) = c_i * (t_a-t_1)\)。\(t_i\)表示第\(i\)次选这个物品的时间。这样，我们只需要为每一个物品找到一个开始和结束时间的时间即可。

由于考虑任意两种物品及其位置对其它的物品的贡献无影响，所以我们考虑任意两种物品。

对于两种物品\(i, j\)，假设\(c_i \ge c_j\)，他们开始和结束时间分别为\(l_i, r_i\)和\(l_j, r_j\)，则最优解中肯定\(l_i < l_j, r_j < r_i\)，证明如下：

首先显然肯定不可能\(l_j < l_i, r_i < r_j\)。

假设\(l_i < l_j, r_i < r_j\)（\(l_j < l_i, r_j < r_i\)证明类似），则可以证明将\(r_i, r_j\)交换后更优（证明大简单，略）。

所以我们将物品排序后，一个个取即可。

题解

所以贪心地取即可

#include 
    
     using namespace std;typedef long long ll;const int N=500005;int n, k, a[N];int main() {    scanf("%d%d", &n, &k);    for(int i=1; i<=k; ++i) {        scanf("%d", &a[i]);    }    sort(a+1, a+1+k);    int num=n-1;    ll ans=0;    for(int i=k; i; --i) {        if(num<0) {            break;        }        ans+=(ll)num*a[i];        num-=2;    }    printf("%lld\n", ans);    return 0;}