CF1472C Long Jumps 题解
Melon_Musk
2021-02-01 08:38:50
[CF1472C Long Jumps题面](https://www.luogu.com.cn/problem/CF1472C)
[安利我的博客](https://www.melonmusk.cn/index.php/2021/02/01/cf1472c-long-jumps-%e9%a2%98%e8%a7%a3/)
## 题面描述
一个长为$ n $的序列$ a $，如果当前在下标$ i $，则下一步会跳到$ i + a[i] $，直到跳出序列。 要求答案即为路径上经过的$ a[i] $之和。现在你可以任意选择起点，求答案的最大值。
## 分析
**一道比较显然的dp题**
对于我们当前所在的位置 $ i $ ，显然它可以转移到 $ i+a[i] $。
令$f[i]$表示到走到当前所在的位置$i$的路径中答案的最大值。
故由题意得转移方程式为：
$f[i+a[i]]=max(f[i+a[i]],f[i]+a[i])$
初始所有$f[i]$均为0。总答案即为所有$f[i]$中的最大值
于是我飞速将此代码码了出来，然后发现它 [RE](https://www.luogu.com.cn/record/45892057) 了。
原因是这题的$a[i]$范围在 $10^9$，我们的$f[i]$直接开数组显然会爆炸！
所以我们可以将$f$数组改为map类型！因为我们的$n$只有$2⋅10^5$，所以可以通过这道题。
[AC记录](https://www.luogu.com.cn/record/45892115)
## 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+7;
ll read()
{
ll res=0,f=1;
char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) res=(res<<1)+(res<<3)+c-48,c=getchar();
return res*f;
}
ll a[maxn];
map<ll,ll> f;
int main()
{
int T=read();
while(T--)
{
int n=read();
ll maxx=0;
f.clear();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
{
f[i+a[i]]=max(f[i+a[i]],f[i]+a[i]);
maxx=max(maxx,f[i+a[i]]);
}
printf("%lld\n",maxx);
}
return 0;
}
```
求点赞awa！