C++(g++ 7.5.0) 解法, 执行用时: 40ms, 内存消耗: 41560K, 提交时间: 2023-05-14 21:37:27

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,k,a[N],dp[105][N];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[1][i]=max(dp[1][i-1],a[i]);
	for(int i=2;i<=m;i++) for(int j=k+1;j<=n;j++) dp[i][j]=max(dp[i][j-1],dp[i-1][j-k]+a[j]);
	cout<<dp[m][n]<<endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 10ms, 内存消耗: 4812K, 提交时间: 2023-05-11 00:00:42

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[10010],dp[110][10010];
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)  cin>>a[i];
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)  dp[1][i]=max(dp[1][i-1],a[i]);
	for(int i=2;i<=m;i++)
		for(int j=k+1;j<=n;j++)
			dp[i][j]=max(dp[i][j-1],dp[i-1][j-k]+a[j]);
	cout<<dp[m][n];
}