Puoi leggere e provare a risolvere il problema ostacoli
visitando la piattaforma Terry.
Hint 1. Programmazione dinamica.
Hint 2. Cerca una soluzione .
Hint 3. È davvero necessario considerare tutte le possibili distanze e tutti i possibili tempi?
Il problema è una classica programmazione dinamica.
Per , denotiamo con la seguente quantità: il massimo numero di punti che Mojito riesce a guadagnare nell'intervallo di tempo , supponendo che salti l'ostacolo (ovvero, che si trovi nel punto all'istante ).
Cerchiamo una ricorrenza per . Consideriamo un , e distinguiamo due casi.
La ricorrenza cercata sarà quindi:
Se nessuna delle condizioni e è verificata, poniamo , dove, nella pratica, è un numero "molto negativo" (ad esempio, va bene ).
Alla fine, la risposta sarà data da
La DP appena descritta ha esattamente stati, e la transizione (ovvero, il calcolo di mediante la ricorrenza determinata prima) richiede tempo . Pertanto, la complessità dell'algoritmo è .
C++
#include <iostream>
#include <vector>
using namespace std;
void solve(int t) {
int N, L, D;
cin >> N >> L >> D;
vector<int> X(N), P(N), S(N);
for (int i = 0; i < N; i++)
cin >> X[i] >> P[i] >> S[i];
const int INF = 1e9;
vector<int> dp(N);
for (int i = 0; i < N; i++) {
dp[i] = -INF;
if (S[i] >= X[i]) dp[i] = max(dp[i], P[i]);
for (int j = 0; j < i; j++)
if (S[i] - S[j] >= abs(X[i] - X[j]))
dp[i] = max(dp[i], dp[j] + P[i]);
}
int ans = 0;
for (int i = 0; i < N; i++)
ans = max(ans, dp[i]);
cout << "Case #" << t << ": " << ans << "\n";
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) solve(t);
return 0;
}