题解 | #牛牛吃草#
牛牛吃草
https://www.nowcoder.com/practice/f05254f070944ff792c0dfefabd94fec
#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数组即可。
投递快手等公司10个岗位
，
查看19道真题和解析