AcWing 3771. 选取石子

这道题很简单,反思,学一下STL容器和哈希表
哈希表在C++中对应的容器是unordered_map

题目

给定 n 个石子,编号为 1~n。

其中第 i 个石子的价值为 ai。

你需要从中任意挑选若干个石子,并将挑选好的石子按照编号从小到大的顺序排成一排。

选中的石子在排好序后需要满足,对于任意两个相邻的石子(不妨设它们的编号为 x,y),x?y=ax?ay 均成立。

例如,当有 n=8 个石子,石子价值分别为 [3,4,4,6,6,7,8,9] 时,一些合理的选择方案如下:

选择 1,2,4 号石子,它们的价值分别为 3,4,6。1 号石子与 2 号石子相邻,2?1=4?3 成立。2 号石子与 4 号石子相邻,4?2=6?4 成立。所以方案合理。
选择 7 号石子。可以只选择一个石子,此时选取任何石子均为合理方案。
你的选择方案不仅需要合理,而且还要使得选中石子的价值总和尽可能大。

请计算并输出价值总和的最大可能值。

输入输出

第一行包含整数 n
第二行包含 n 个整数 a1,a2,…,an。
输出:一个整数,表示选中石子的价值总和的最大可能值。

思路

x?y=ax?ay,即 ax - x == ay - y
将ax - x 看作每个元素的树形,用哈希表h[ax - x] += ax
最后答案为哈希表中最大的元素

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;
const int N = 200010;

int main()
{
    unordered_map<int,LL> h;
    unordered_map<int,LL>::iterator it;
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        int x;
        cin >> x;
        h[x - i] += x;
    }
    LL res = 0;
    for(it = h.begin();it != h.end();it ++){
        res = max(res,it->second);
    }
    cout << res;
    return 0;
}

AcWing 3771. 选取石子

上一篇:windows下实现uboot的tftp下载功能


下一篇:ps下通过图层样式制作剔透的绿色水晶字