应该是01背包问题的变种吧

我们这个题，它不是连续的取值了。但是又是从中挑值。因为我也巨垃圾，一直没体会到含义。

dp分析思路如下

我们的01背包问题是，从前$i$个里面挑取不定个，然后要使我们的价值最大且体积不超过。

我们这个问题是，挑出来$m$个数的序列，让它们的加权和最大。所以我们就需要更改在01背包问题中集合的含义。

在本题中$F[i][j]$代表从前$i$个数中选择$j$个他们的加权和最大。

状态转移

我们对于第$i$个数，我们都存在选取它与不选取它的抉择。

那么我们如果不选取它的话我们的加权和应该是来自上一个也就是从$(i-1)$个数中选的最大值所以是。

$F[i][j] = F[i-1][j]$。

但是我们如果选取它的话，我们便成了。 $F[i-1][j-1] + j * a[i]$

我们$j$的含义是，选取了$j$个那么当前选的这个数一定是第$j$个，如果不选它的话，之前一定是$i - 1$个数加权，正因为它是第$j$个，所以便成了$j * a[i]$才符合我们的题意。 （其实这么一套下来，就是闫式dp分析法。。我没画图） 我认为最最精髓的是，对于$j$的定义，是拿到了$j$个数

代码实现O(nm)

#include<iostream>
#include<cstring>
using namespace std;


const int N = 2010;
int a[N];
long long f[N][N] = {0};
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    //初始化dp数组，因为存在全负
    memset(f, -0x3f, sizeof f);
    for(int i = 0; i <= n ; i++)
        f[i][0] = 0;     //在拿了0个数的时候和一定是0
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)  //因为我们最多只需要拿到m个数字
        {
            f[i][j] = max(f[i-1][j], f[i-1][j-1] + j * 1ll * a[i]);    //根据状态转移公式抄过来
        }
    cout<<f[n][m];  //从前n个拿到m个数的加权和最大
    return 0;
}