dp[i][j]表示第i次跳跃到达j位置的最优解
思路即代码
#include <iostream> #include <stdio.h> #include <algorithm> #include <map> #include <queue> #define ll long long #include<set> #include<string.h> #include<math.h> #include<istream> using namespace std; #define inf 0x3f3f3f3f inline ll read() { ll k = 0, f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { k = k * 10 + ch - '0'; ch = getchar(); }return k * f; } #define mod 998244353 ll a[1005]; ll dp[1005][1005]; int main() { ll n=read(),p=read(),t=read(); for(int i=1;i<=n;i++)a[i]=read(),dp[0][i]=-inf; dp[0][0]=0; dp[0][n+1]=-inf; a[0]=0; a[n+1]=0; for(int i=1;i<=t;i++) { for(int j=0;j<=n+1;j++)dp[i][j]=-inf; for(int j=i;j<=min(n+1,i*p);j++) { for(int k=max(i-1,int(j-p));k<j;k++) { dp[i][j]=max(dp[i][j],dp[i-1][k]+a[j]); } } } cout<<dp[t][n+1]<<'\n'; }