[GESP202406 四级] 宝箱题解

DoubleQLzn · 2024-10-24 13:16:05 · 个人记录

本篇题解所用知识点:

• 【3】递推法

首先，我们可以用 f_i 表示选择 i 的得分，那么 f_i 就相当于 i 的出现次数乘 i，因此可以在输入时直接做处理，每次输入 a_i 后让 f_{a_i} 加上 a_i。

接着，我们可以枚举每个区间 [l,l+k]，可以得到的答案就是 f_l+f_{l+1}+\cdots +f_{r-1}+f_r。不难想到用前缀和优化优化求区间和。

由于每个 l+k 确定，所以直接枚举 l 即可，由于区间和已经优化至 O(1)，所以时间复杂度是 O(n)，由于输入 n 个数，已经无法优化。

Code

#include <bits/stdc++.h>
using namespace std;
long long f[2005],sum[2005],a[2005];
int main()
{
    long long n,k,ma = 0;
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
        f[a[i]] += a[i];
    }
    for (int i = 1;i <= 1000;i++)
    {
        sum[i] = sum[i - 1] + f[i];
    }
    for (int i = 1;i <= 1000;i++)
    {
        ma = max(ma,sum[i + k] - sum[i - 1]);
    }
    cout << ma;
    return 0;
}