CF1472C Long Jumps

Polycarp found under the Christmas tree an array a of n elements and instructions for playing with it:

• At first, choose index $i$ $(1≤i≤n)$ — starting position in the array. Put the chip at the index $i$ (on the value $a_i$).
• While $i≤n$, add $a_i$ to your score and move the chip $a_i$ positions to the right (i.e. replace $i$ with $i+a_i$).
• If $i>n$, then Polycarp ends the game.
  For example, if $n=5$ and $a=[7,3,1,2,3]$, then the following game options are possible:
• Polycarp chooses $i=1$. Game process: $i = 1 \overset{+7}{\longrightarrow} 8$. The score of the game is: $a_1=7$.
• Polycarp chooses $i=2$. Game process: $i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$. The score of the game is: $a_2+a_5=6$.
• Polycarp chooses $i=3$. Game process: $i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$. The score of the game is: $a_3+a_4=3$.
• Polycarp chooses $i=4$. Game process: $i = 4 \overset{+2}{\longrightarrow} 6$. The score of the game is: $a_4=2$.
• Polycarp chooses $i=5$. Game process: $i = 5 \overset{+3}{\longrightarrow} 8$. The score of the game is: $a_5=3$.
  Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way.

Input

The first line contains one integer $t$ $(1≤t≤10^4)$ — the number of test cases. Then $t$ test cases follow.
The first line of each test case contains one integer $n$ $(1≤n≤2⋅10^5)$ — the length of the array $a$.
The next line contains $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i≤10^9)$ — elements of the array $a$.
It is guaranteed that the sum of n over all test cases does not exceed $2⋅10^5$.

Output

For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from $1$ to $n$ in such a way as to maximize his result.

Example

input

4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1

output

7
6
1000
5

Note

The first test case is explained in the statement.
In the second test case, the maximum score can be achieved by choosing $i=1$.
In the third test case, the maximum score can be achieved by choosing $i=2$.
In the fourth test case, the maximum score can be achieved by choosing $i=1$.

Translation

给一个数组 $a$，选择一个索引 $i$。从 $i$ 开始，获得收益 $a_i$，再执行操作 $i:=i+a_i$，直到 $i>n$ 时停止。求能够获得的最大收益。

Idea

正解

正常做从头开始模拟显然会 $\text{TLE}$，于是我们倒过来求：让 $a_i$ 加上本身的位置 $i$，如果大于 $n$ 舍弃，否则就让 $a_{i+a_i}$ 叠加上原有数组中 $a_i$ 的值，在这些值中找最大即可。

歪解

选择一个索引 $i$，就会形成一条形如 $i\to i+a_i\to i+a_i+a_{i+a_i}\to\cdots$ 的路径。数组的元素个数为 $n$，将 $i>n$ 的情况归为一点 $n+1$；按照路径建边，点的编号为数组索引，从点 $i$ 出发的边边权为 $a_i$。例如样例 $a=[2,2,1,2,3,3]$，建图如下。

题目的本质是求图上的最长路径长度。由于是 $\text{DAG}$，可以考虑拓扑排序后再动态规划：设 $MaxDis_i$ 表示以点 $i$ 结束的最长路径长度，那么对于一条边 $(u,v)$，可以进行多次松弛操作 $MaxDis_v=\max\{MaxDis_u+w(u,v),MaxDis_v\}$，$MaxDis_{n+1}$ 即为答案。

Code

正解

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1472C
Date: 01/13/2020
Description: Graph Theory, Dynamic Programming
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200020;
int _;
int n;
ll a[N];
int main(){
	for(cin>>_;_;_--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		ll ans=0;
		for(int i=n;i>=1;i--){
			if(i+a[i]<=n){
				//叠加上贡献
				a[i]+=a[i+a[i]];
			}
			ans=max(ans,a[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

歪解

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1472C
Date: 01/13/2020
Description: Graph Theory, Dynamic Programming
*******************************************************************/
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=200020;
int _;
int n;
int indeg[N];//入度
int TopoOrder[N];//拓扑序
ll MaxDis[N];//最长路径长度
struct EDGE{
	int to;
	int Next;
	ll w;
}edge[N<<1];
int head[N],tot;
inline void INIT();
inline void add_edge(int,int,ll);
void TopoSort();
ll DP();
int main(){
	for(cin>>_;_;_--){
		cin>>n;
		INIT();
		ll ans=0;
		for(int i=1;i<=n;i++){
			ll a;
			cin>>a;
			//建边
			add_edge(i,min(i+a,(ll)n+1),a);
			indeg[min(i+a,(ll)n+1)]++;
		}
		TopoSort();//拓扑排序
		cout<<DP()<<endl;//DP
	}
	return 0;
}
inline void add_edge(int u,int v,ll w){
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	edge[tot].w=w;
	head[u]=tot;
}
inline void INIT(){//初始化
	memset(indeg,0,sizeof(int)*(n+5));
	memset(head,-1,sizeof(int)*(n+5));
	memset(MaxDis,0,sizeof(ll)*(n+5));
	tot=0;
}
void TopoSort(){
	queue<int>q;
	int num=0;
	for(int i=1;i<=n+1;i++){
		if(!indeg[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		TopoOrder[++num]=x;//获取拓扑序列
		for(int i=head[x];~i;i=edge[i].Next){
			int y=edge[i].to;
			indeg[y]--;
			if(!indeg[y]){
				q.push(y);
			}
		}
	}
}
ll DP(){
	for(int i=1;i<=n+1;i++){
		int x=TopoOrder[i];
		for(int j=head[x];~j;j=edge[j].Next){
			int y=edge[j].to;
			//松弛操作
			MaxDis[y]=max(MaxDis[y],MaxDis[x]+edge[j].w);
		}
	}
	return MaxDis[n+1];
}