526互联

Codeforces Round 625 (Div. 1, based on Technocup 2020 Final Round) A. Journey Planning（dp）

发布时间 2023-04-17 21:21:49作者: 高尔赛凡尔娟

https://codeforces.com/contest/1320/problem/A

A. Journey Planning

题目大意：

给定一组数，问我们ai-aj==i-j的时候就可以把ai的值加起来，问我们可以凑到的最大总值是多少？

input 
6
10 7 1 9 10 15
output 
26

input 
1
400000
output 
400000

input 
7
8 9 26 11 12 29 14
output 
55

思路：
虚拟一个源点下标为0，值为0
每次和前面或者后面相差的数字
其实就可以倒回来和0位置上的数字作比较
全部都凑到某个位置上加起来的总值，就是我们要的最大值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=4e5+10,M=4023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
unordered_map<LL,LL> mp;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            LL x;
            cin>>x;
            mp[x-i]+=x;
        }
        LL maxn=0;
        for(auto [key,val]:mp)
        {
            maxn=max(maxn,val);
        }
        cout<<maxn<<endl;
    }
    return 0;
}