题意

• 共有0~30000编号的岛，有n个宝藏，你每次只能往编号大的方向走，走的步长只能是上一次走的步长+p（p=-1,0,1），第一步走了d，求最多能拿到多少宝藏

思路

• 本题应该使用dfs+剪枝是更好写的
• dp
  • 对于0~30000这个范围，从1开始走，最大的偏移量不超过300
  • 即相较于第一步d，最后一步的步长一定在d-300~d+300之间
  • 对于每一步，都有可能从任何一个偏移量的步数走来，需要维护一个二维dp数组
  • 
  • 上一步走了j走到第i座岛屿能拿到的最多宝藏，是从上上步走了j+1，j，j-1走到i-j的最大宝藏数+i处的宝藏数
  • 由于数组不方便开负的，所以要把所有的偏移量加上一个base
  • 初值： 第一步已经走了，，只有从这个位置往后转移的才是有效值，所以除了这个位置都赋无穷小

AC代码

#include<bits/stdc++.h>
using namespace std;

int p[30303];
int dp[30303][620];


int main(){
    int base=300;
    int n,d;
    cin >> n >> d ;
    for(int i=1;i<=n;i++){
        int tp;
        cin >> tp ;
        p[tp]+=1;
    }

    memset(dp,-0x3f3f,sizeof(dp));
    int ans=dp[d][base]=p[d]+p[0];

    for(int i=d+1;i<=30000;i++){
        for(int j=-300;j<=300;j++){
            if(d+j>0&&d+j<=i){
                dp[i][base+j]=max(dp[i][base+j],max(dp[i-(d+j)][base+j],max(dp[i-(d+j)][base+j-1],dp[i-(d+j)][base+j+1]))+p[i]);
            }
            ans=max(ans,dp[i][base+j]);
        }
    }
    cout << ans << endl;
    return 0;
}