C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 488K, 提交时间: 2019-01-05 13:23:45

#include<bits/stdc++.h>
using namespace std;
const int maxn=4005,inf=1e8;
int d[maxn],a[maxn],n,k,w;
int main()
{
	cin>>n>>k>>w;
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int i=1;i<=w;i++)d[i]=-inf;
	d[k]=k*a[0];
	for(int i=1;i<n;i++)a[i]-=a[0];
	for(int i=k+1;i<=w;i++)
	for(int j=1;j<min(n,i-j+1);j++)
	d[i]=max(d[i],d[i-j]+a[j]);
	cout<<d[w];
}

C++(clang++ 11.0.1) 解法, 执行用时: 6ms, 内存消耗: 432K, 提交时间: 2022-09-20 10:22:07

#include<bits/stdc++.h>
using namespace std;
int f[10005];
int p[10005];
int main()
{	int n,k,w;
	cin>>n>>k>>w;
		for(int i=0;i<n;i++)
		{	cin>>p[i];
			if(i)
			p[i]-=p[0];
		}
		f[0]=k*p[0];
		for(int i=1;i<=n;i++)
			for(int j=i;j<=w-k;j++)
				f[j]=max(f[j],f[j-i]+p[i]);
				cout<<f[w-k]<<endl;
}

Python3 解法, 执行用时: 1332ms, 内存消耗: 4976K, 提交时间: 2023-08-04 13:59:05

n, k, w = map(int, input().split())
a = list(map(int, input().split()))
dp = [-float('inf')] * (w+1)
dp[0] = 0

for i in range(1, n):
    a[i] -= a[0]

w -= k

for i in range(1, n):
    for j in range(i, w+1):
        dp[j] = max(dp[j-i] + a[i], dp[j])

print(dp[w] + k*a[0])