题目描述
示例
提示
感想&&思路
好几天没打代码，脑子都生锈了（其实是在打游戏）
这个题的大体意思就是从1到n中找到某个位置作为切入点，之后这个位置加上这个位置上的值，如果还在1到n之间，就重复上述操作
最后的答案应该是位置上的值相加
找到最大的这个答案
一开始想了个加算法结果wa了，没有考虑全面
之后脑子一抽写了一个暴力，果然tle了
正确的思路如下：
从倒数第二个值开始判断a[i]+i是否<=n如果是的话，就把下一个位置的值累加到这个位置的值上去
最后从第一个位置遍历到最后一个位置，找到最大值输出
至于为什么是从后向前找，因为每个a[i]必定是大于1的，他的下一个位置一定是在他之后，所以要反向累加
AC代码
#include<bits/stdc++.h> using namespace std; long long a[200010],b[200010]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); b[i]=a[i]; } for(int i=n-1;i>=0;i--) { if(a[i]+i<=n) b[i]=max(b[i],b[i]+b[a[i]+i]); } long long ans=0; for(int i=1;i<=n;i++) ans=max(ans,b[i]); printf("%lld\n",ans); } return 0; }