CF505C Mr. Kitayuta, the Treasure Hunter 题解

违规用户名1529916 · 2026-07-20 15:44:03 · 题解

洛谷题目传送门

CF 题目传送门

解法

显然可以用 dp 来做。一个朴素的 dp 是记 dp[i,j] 为现在在第 i 个岛屿且上一步跳跃了 j 距离时能最多收集到的宝石的数量，即

显然 O(n^2) 的空间会 MLE，所以我们需要优化这个柿子。

注意到 \displaystyle\sum j 不会超过 n，即 j 的上界大概是 \sqrt n 左右。

于是我们只需要维护每个 j 与 d 间的偏移量即可。

令最大的偏移量为 \Delta，可列出方程 \displaystyle\frac{\left(\Delta+1\right)\left(2d+\Delta\right)}2=n，显然 d 最小取 1 时 \Delta 有最大值约是 250 左右，即 \Delta 的区间是 \left[-250,250\right]。

记得偏移下标和记录不可达状态，dp 一下就做完了。

时间复杂度 O(n\sqrt n)。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+5,MAXD=1005,OFFSET=500,INF=0x3f3f3f3f;
int n,d,ans,p[MAXN],cnt[MAXN],dp[MAXN][MAXD];
int main(){
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
        cnt[p[i]]++;
    }
    memset(dp,-INF,sizeof(dp));
    ans=dp[d][OFFSET]=cnt[d];
    for(int i=d+1;i<MAXN;i++){
        for(int j=0;j<MAXD;j++){
            int l=d+j-OFFSET;
            if(l<=0||i-l<d) continue;
            if(j>0&&l>1) dp[i][j]=max(dp[i][j],dp[i-l][j-1]);
            dp[i][j]=max(dp[i][j],dp[i-l][j]);
            dp[i][j]=max(dp[i][j],dp[i-l][j+1]);
            dp[i][j]+=cnt[i];
            ans=max(ans,dp[i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}

:::