题解 | #牛牛吃草#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> w(n),a(n);
    for(int i=0;i<n;i++) cin>>w[i];
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=w[0];
    for(int i=1;i<n;i++){
        int maxnum=0;
        for(int j=0;j<i;j++) if((i-j)%a[j]==0) maxnum=max(maxnum,w[j]);
        w[i]+=maxnum;
        ans=max(ans,w[i]);
    }
    cout<<ans<<endl;
    return 0;
}

动态规划，dp[i]表示在i停止时，最多可以吃多少。对于每个dp[i]，只需要遍历之前的dp[j] (j<i)，对于能走到i的那些(即满足(i-j)%a[j]==0)，记录他们的最大值，该最大值+w[i]即为dp[i]。这里其实不需另设dp，直接将w数组用作dp数组即可。