D - Index × A(Not Continuous ver.)

传送门 

思路：经典01背包小变形，N为物品数量代替体积V, 价值变成了i * a[i]；

​
#include
using namespace std;
 
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
 
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 2010;
 
ll a[N];
ll dp[N][N];
 
int main()
{
	IOS;
	int n, k;
	cin >> n >> k;
	dp[0][0] = 0;
    for (int j = 1; j <= k; ++j) dp[0][j] = -1e16;
	repn(i, 1, n)
		cin >> a[i];
 
	repn(i, 1, n)
		repn(j, 1, k)	dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i] * 1ll * j);
 
	cout << dp[n][k] << endl;
 
	return 0;
}
 
​