每日一题 Mr. Kitayuta, the Treasure Hunter (线性dp)

一.题意

二.题解

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9')
{if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',
ch=getchar();return s*w;}
ll qpf(ll a, ll b, ll p)
{ll ret = 0;while(b){if(b & 1) ret = (ret + a) % p;
a = (a + a) % p;b >>= 1;}return ret % p ;}
ll qp(ll a, ll n, ll p)
{ll ret = 1;while(n){if(n & 1) ret = qpf(ret, a, p);a = qpf(a, a, p);
n >>= 1;}return ret % p ;}

const int manx=3e4+5;
const int N=5e2+5;
const int mod=1e9+7;
const int mo=998244353;

ll dp[manx][505];
ll cnt[manx];
ll n,d,ans;

int main(){
    memset(dp,-1,sizeof(dp));
    n=read(),d=read();
    for(int i=1;i<=n;i++){
        ll x=read(); cnt[x]++;
    }
    ans=dp[d][250]=cnt[d];
    for(int i=d;i<=30000;i++){
        for(int j=1;j<=500;j++){
            if(dp[i][j]==-1) continue;
            int nx=d+i+j-250;
            for(int k=-1;k<=1;k++)
                if(nx+k<=30000&&j+k>0&&nx+k>i) 
                    dp[nx+k][j+k]=max(dp[nx+k][j+k],dp[i][j]+cnt[nx+k]),
                    ans=max(ans,dp[nx+k][j+k]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}