P1725 琪露诺

题目大意

在一条直线（或编号轴）上从起点出发，每次可以从位置 $j$ 跳到 $i$，要求跳跃长度在区间 $[l, r]$ 内。每到达一个位置会获得或损失对应的分值。问到达“终点对岸”（位置编号超过 $n$）时，能得到的最大总分。

AC代码

比较裸的子序列提取dp（子序列为 [ i-r , i-l ] ），唯一需要注意的是

只要她下一步的位置编号大于N就算到达对岸。

所以你的dp范围要扩大一点

#include <iostream>
using namespace std;
typedef long long ll;
const ll N=4e5+10,inf=1e18+7;
ll n,l,r,A[N],dp[N],ans=-inf;    // dp存的是走到该点最多能够获得多少冰冻指数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    // 移动到i+L,i+R 向前递增，无后效性
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++) {
        cin>>A[i];
    }
    dp[0]=A[0];
    for(int i=1;i<=n+r;i++) {
        dp[i]=-inf;
    }
    for(int i=1;i<=n+r;i++) {
        for(int j=i-l;j>=i-r && j>=0;j--) {
            dp[i]=max(dp[j]+A[i],dp[i]);
        }
    }
    for(int i=n;i<=n+r;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183798861

心路历程（WA，TLE，MLE……）