NC110793（Mr. Kitayuta, the Treasure Hunter ）

感受


思路



开始转入正题

int get(int dis){
    return dis - d + 250;
}

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 30000 + 10;
int n, d, m;
int cnt[maxn];
int dp[maxn][600];
int get(int dis){
    return dis - d + 250;
}
int main(){
    scanf("%d%d", &n, &d);
    int val;
    for(int i = 1; i <= n; i++){
        scanf("%d", &val); cnt[val]++;
    }
    m = 30000;
    for(int i = m; i >= d; i--){
        for(int j = d - 250; j <= d + 250; j++){
            dp[i][get(j)] = cnt[i];
            if(i + j >= 0 && i + j <= m && i + j > i){
                dp[i][get(j)] = max(dp[i][get(j)], dp[i + j][get(j)] + cnt[i]);
            }
            if(i + j - 1 >= 0 && i + j - 1 <= m && i + j - 1 > i){
                dp[i][get(j)] = max(dp[i][get(j)], dp[i + j - 1][get(j - 1)] + cnt[i]);
            }
            if(i + j + 1 >= 0 && i + j + 1 <= m && i + j + 1 > i){
                dp[i][get(j)] = max(dp[i][get(j)], dp[i + j + 1][get(j + 1)] + cnt[i]);
            }
        }
    }
    printf("%d\n", dp[d][get(d)]);
    return 0;
}