参考：
https://matiji.net/exam/brushquestion/74/4009/C448715ED43BEA9D2D47CED523050945
https://www.bilibili.com/video/BV1RR4y1Q7jL/?t=1672.2&vd_source=de3426defac834fbf1e8309c305e87aa

问题引入

小码哥很喜欢吃蛋糕。某一天，他来到了一条神奇的街上，这里依次开了 $n$ 家蛋糕店，每家蛋糕店只售卖一种类型的蛋糕。第 $i$ 家蛋糕店售卖的蛋糕拥有 $a_i$ 的饱腹值和 $b_i$ 的美味值。

小码哥从第一家蛋糕店开始向前行走。当他到达一个蛋糕店时，若他当前未处于饱腹状态，则会考虑是否吃这家店的蛋糕。若他在第 $i$ 家店吃了一个拥有 $a_i$ 饱腹值的蛋糕，则接下来从第 $i+1$ 到第 $i＋a_i$ 家店他都不会吃任何东西。特别地，若 $i＋a_i$ 大于 $n$ ，则他之后将会一直处于饱腹状态。

小码哥想知道，在满足上述要求的情况下，他能够吃到的蛋糕的美味值之和最大可以是多少。

输入格式：
第一行输入一个整数n(1≤n ≤2000)，表示蛋糕店个数。
接下来一行输入n个整数a1, a2,…· ,an(1 ≤a≤n)，依次表示每家店蛋糕的饱腹值。
最后一行输入n个整数 b1, b2, …· ,bn(1 ≤bi≤104)，依次表示每家店蛋糕的美味值。
输出格式:
输出一个整数，表示最大美味值之和。

输入:
6
2 1 1 1 1 2
1 10 5 8 5 7
输出：
25

备注：
对于样例，依次吃第2、4、6家店的蛋糕可以得到最大美味值之和。

问题分析

采用逆推，从最后一家店往回推算。

设 $f[i]$ 为“从第 $i$ 家开始，所能得到的最大美味值”。则易知，对于第 $n+1$ 家蛋糕店,因为第 $n+1$ 家蛋糕店不存在，所以有 $f[n+1] = 0$ .

而对于第 $n$ 家蛋糕店，显然有 $f[n] = b_n$ .

再讨论 $f[i]$ ，这里需进行分类：

小码哥吃了第 $i$ 家的蛋糕。那么接下来的 $a_i$ 家蛋糕店，小码哥都不能光顾，直至第 $a_i + 1$ 家蛋糕店。所以有 $f[i] = b_i + f[i+a_i + 1]$ .
注意： $i+a_i + 1 >= n+1$ 时，其 $f$ 值为0 。
小码哥没吃第 $i$ 家的蛋糕。那么此时相当于小码哥从第 $i + 1$ 家蛋糕店出发，此时有 $f[i] = f[i + 1]$ .

当然，由于 $f[i]$ 是要求最大美味值，所以需对上述两类进行比较，最终将最大者赋给 $f[i]$ 。

而这里还需定义一个 $ans$ 变量，用以存储最终答案。在每个 $f[i]$ 求出来时，都要进行两者的比较，以便对 $ans$ 进行更新。

题解代码

#include<stdio.h>
#define MAX 2010

//思想：从第n家往第1家逆推 
int n, a[MAX], b[MAX], f[MAX];

int main() 
{
    int i,ans=0;
    int c;
    scanf("%d",&n);

    for(i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;++i)
    {
        scanf("%d",&b[i]);
    }
    f[n+1]=0;
    //逆推
    for(i=n;i>=1;--i)
    {
        c = i+a[i]+1;
        if(c >= n+1)
        {
            c = n+1;
        }
        if(f[i+1] >= f[c]+b[i])
        {
            f[i]=f[i+1];
        }
        else
        {
            f[i]=f[c]+b[i];
        }
        if(f[i] >= ans)
        {
            ans = f[i];
        }
    }
    printf("%d",ans); 
    return 0;
}

OvO