CF1472C Long Jumps 题解

CF1472C Long Jumps题面

安利我的博客

题面描述

一个长为 n 的序列 a ，如果当前在下标 i ，则下一步会跳到 i + a[i] ，直到跳出序列。 要求答案即为路径上经过的 a[i] 之和。现在你可以任意选择起点，求答案的最大值。

分析

一道比较显然的dp题

对于我们当前所在的位置 i ，显然它可以转移到 i+a[i] 。

令f[i]表示到走到当前所在的位置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;
}

求点赞awa！