Codeworks round 693 (Div. 3) C. long jumps problem solution

Codeforces Round #693 (Div. 3) C. Long Jumps

The original question is here ！

---

The main idea of the topic

​ Polycarp Playing a game , Given that there is n Array of elements a, Set a starting point i. When i <= n when , i = i + a[i], score score = score + a[i], Try to find out for the array a The maximum score that can be obtained .

---

analysis

​ First of all, this question has a large amount of data , time limit 2s, Violent solution is affirmative ⑧ Yes .

​ Observe the topic carefully , For each assumed starting value i , There are two cases ：

• i + a[i] > n , At this time, its score ans = a[i].

• i + a[i] <= n , The game is not over i = i + a[i] , score ans += a[i] , And the next round , until i + a[i] > n until .

  ​ If we're from i = n To traverse the , And will a[i] Your scores are stored in a[i] in , Even if i + a[i] <= n The situation of , Its a[i+a[i]] Your score has been calculated , You don't need to start from scratch .

  ---

  The code is as follows

  #include<bits/stdc++.h>
  
  using namespace std;
  const int N = 2*1e5+10;
  
  int main(){
    
  	int t;
  	cin >> t;
  	for(int p = 0;p < t;p++){
    
  		long long a[N],n,maxn = 0;
  		cin >> n;
  		for(int i=1;i<=n;i++) cin >> a[i];
  		for(int i = n;i > 0;i--){
    
  			if(i+a[i]<=n) a[i] += a[i+a[i]];
  			if(a[i] > maxn) maxn = a[i];
  		}
  		cout << maxn << endl;
   	}
      return 0;
  }

---

END