题解 | #牛牛吃草#

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> w(n);

    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> f(n);
    for (int i = 0; i < n; i++) {
        f[i] = w[i];
    }

    for (int i = 0; i < n; i++) {
        int maxj = 0;
        for (int j = 0; j < i; j++) {

            if ((i - j) % a[j] == 0) {
                if (f[j] > maxj) {
                    maxj = f[j];
                }
            }
        }
        f[i] = w[i] + maxj;

    }
    auto maxPosition = max_element(f.begin(),f.end());
    cout<< *maxPosition;

    return 0;


}
// 64 位输出请用 printf("%lld")

很经典的DP思路，关键在于设计状态量

选择到达第n块最大吃草量作为状态

状态转移方程为f(n)=w(n) + max(f(j)) ((n-j)%a[j]==0）

类似于小青蛙跳台阶的思路，以前青蛙一次只能跳一个格子或者两个格子，所以到达第n块只有两种选择，而现在，选则的个数取决于(n-j)%a[j]==0成立的个数