C++14(g++5.4) 解法, 执行用时: 34ms, 内存消耗: 376K, 提交时间: 2020-01-16 20:48:57

# include <iostream>
# include <algorithm>
# include <cstring>

const int MAXN = 1e3 + 5;
const int NINF = 0xc0c0c0c0;
int v[MAXN];
int dp[MAXN];
int n;
int s;
int t;

int fmax(int num) {
	int max = NINF;
	for (int i=num-t; i<=num-s; i++) {
		if (i>=1 && dp[i] > max) {
			max = dp[i];
		}
	}
	
	return max;
}

int main() {
	int T;
	std::cin >> T;
	while (T--) {
		memset(dp, 0xc0, sizeof(dp));
		std::cin >> n >> s >> t;
		for (int i=1; i<=n; i++) {
			std::cin >> v[i];
		}
		
		dp[1] = v[1];
		for (int i=2; i<=n; i++) {
			if (fmax(i) == NINF) {
				dp[i] = NINF;
			} else {
				dp[i] = fmax(i) + v[i];
			}
		}
		
		if (dp[n] != NINF) {
			std::cout << dp[n] << "\n";
		} else {
			std::cout << "-1\n";
		}
	}
	
	return 0;
}

C++ 解法, 执行用时: 20ms, 内存消耗: 432K, 提交时间: 2021-05-25 09:00:26

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int v[N],dp[N],s,t;
int main()
{
	int T,n,s,t;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&s,&t);
		for(int i=1;i<=n;++i)
			scanf("%d",&v[i]);
		memset(dp,-1,sizeof(int)*(n+1));
		dp[1] = v[1];
		for(int i=2;i<=n;++i)
		{
			for(int j=s;j<=t;++j)
			{
				if(i<=j||dp[i-j]==-1) continue;
				dp[i] = max(dp[i],dp[i-j]+v[i]);
			}
		}
		printf("%d\n",dp[n]);
	} 
	
	return 0;
} 

Python3 解法, 执行用时: 277ms, 内存消耗: 7116K, 提交时间: 2021-10-19 20:58:41

T=int(input())
for i in range(T):
    n,s,t=map(int,input().split())
    lb=list(map(int,input().split()))
    dp=[-1 for i in lb]
    dp[0]=lb[0]
    for i in range(n):
        for j in range(s,t+1):
            if i<j or dp[i-j]==-1:
                continue
            dp[i]=max(dp[i],lb[i]+dp[i-j])
    print(dp[-1])