Ho “risolto” questo problema su codeforces, almeno in teoria.
Il problema consiste nel trovare il maggior numero di gemme che possono essere raccolte lungo un rettilineo lungo 30001 isole (da 0 a 30000), inizialmente si parte dall’isola 0 e si fa un salto lungo d (1 <= d <= 30000) ogni salto successivo a questo può essere lungo uguale a quello precedente, o avere la stessa lunghezza ± 1.
Spiegazione:
si utilizza una dp i,j dove i indica la posizione sul rettilineo e j indica il salto con cui sei arrivato a questa posizione (i salti possibili sono solo [d-246, d+246] )
Il problema è che sul quarto testcase ricevo un output sbagliato, ovviamente ho guardato la soluzione e ho anche rannato il mio codice insieme a quello della soluzione su migliaia di testcases generati randomicamente e sempre hanno generato gli stessi risultati. Ho paura che la colpa sia della differenza tra i compilatori utilizzati sulla piattaforma e sul mio pc.
mio codice:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
int nxt() {int x;cin >> x;return x;}
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
rep(i,t){
solve();
}
}
void solve(){
int n,d;
cin>>n>>d;
// vector<int> arr(30001); //you can use both this commented code or the one below it (one is push dp the other pull dp) in both cases the output to testcase 4 is 19078 instead of 22500
// rep(i,n)arr[nxt()]++;
// int mini = d,maxi = d;
// int cur = d;
// while(cur <= 30000 && mini > 1)cur += --mini;
// cur = d;
// while(cur <= 30000)cur += ++maxi;
// vector<vector<int>> dp(30001,vector<int>(maxi-mini+1,-1));
// dp[d][d-mini] = arr[d];
// rep(i,30001){
// rep(j,maxi-mini+1)if(dp[i][j] != -1 && i + j + mini -1 <=30000){
// rep(z,3)if(i + j + mini -1 + z <= 30000 && j -1 + z >= 0)dp[i+j+mini-1+z][j-1+z] = max(dp[i+j+mini-1+z][j-1+z], dp[i][j] + arr[i+j+mini-1+z]);
// }
// }
// int ans = 0;
// for(auto x : dp[30000])ans = max(ans,x);
// cout<<ans<<endl;
vector<int> arr(30001);
rep(i,n)arr[nxt()]++;
int average = 250;
vector<vector<int>> dp(30001,vector<int>(average*2,-1));
dp[d][average] = arr[d];
rep(i,30001)for(int j =1; j<2*average;j++)if(d - average + j > 0 && i - (d - average + j) >= 0){
int jumpf = d - average + j;
if(i-jumpf>=0)rep(z,3){
int jump = jumpf - 1 + z;
if(jump > 0 && jump - d + average < 500 && dp[i-jumpf][jump-d+average] != -1)dp[i][j] = max(dp[i][j], dp[i - jumpf][jump - d + average] + arr[i]);
}
}
int ans = 0;
for(auto x : dp[30000])ans=max(ans,x);
cout<<ans<<endl;
}