CF1472C Long Jumps 题解

CF1472C Long Jumps题面

题面描述

一个长为 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 了。

原因是这题的 a[i] 范围在 10^9，我们的 f[i] 直接开数组显然会爆炸！

所以我们可以将 f 数组改为map类型！因为我们的 n 只有 2⋅10^5 ，所以可以通过这道题。

AC记录

完整代码

#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;
}