#include<bits/stdc++.h> using namespace std; typedef long long int ll; ll w[1005]; ll dp[1005][1005]; ll n,p,t; const ll inf=0x3f3f3f; int main(){ cin>>n>>p>>t; for(int i=1;i<=n;i++)cin>>w[i]; for(int i=n-p+1;i<=n;i++)dp[i][1]=w[i];///利用跳数为1且可达时的这些点进行递推 for(int i=n;i>=0;i--){ for(int j=2;j<=t;j++){///最后到达剩余1次跳数的格子 dp[i][j]=-inf;///先置为无法到达(跳数过多or跳数过少） for(int k=1;k<=p&&i+k<=n;k++){ dp[i][j]=max(dp[i][j],dp[i+k][j-1]); } if(dp[i][j]!=-inf)dp[i][j]+=w[i];///如果可以到达，加上本身的格子 } } cout<<dp[0][t]<<endl;///从0位置花费t次到达另一边 return 0; }
也可以记忆化搜索
#include<bits/stdc++.h> using namespace std; typedef long long int ll; ll w[1005]; ll dp[1005][1005]; ll n,p,t; const ll inf=0x3f3f3f; ll maxx=-inf; int dfs(int m,int step){ if(m>n+1||step<0)return -inf;///超过位置or步数不足 if(step>n+1-m)return -inf;///剪枝，步数过多 if(dp[m][step]!=-1)return dp[m][step];///更新过最优值，直接返回 if(step==1){///剩余1步时 if(n+1-m<=p)return dp[m][step]=w[m]; else return -inf;///不在最后p格中返回不可达 } int sum=-inf; for(int i=1;i<=p;i++){ sum=max(sum,dfs(m+i,step-1)); } if(sum!=inf)sum+=w[m];///加上本身的权值 return dp[m][step]=sum; } int main(){ cin>>n>>p>>t; memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++)cin>>w[i]; cout<<dfs(0,t)<<endl; return 0; }
原文：https://www.cnblogs.com/mohari/p/13541923.html
