Aiuto per Trasporto tronchi (oii_alberi)

Chiarimenti
1

Ciao a tutti, stavo risolvendo il problema Trasporto tronchi.
Ho creato un codice che mi da 100/100, tuttavia penso che sia comunque sbagliato.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long carica(int N, int K, vector<int> A) {
	ll ans = 0;
	for(int i = 0; i < N; i++){
		if(A[i] < K) ans += A[i];
		else{
			if(i == N - 1){
				ans += A[i];
			}
			else{
				ans += 1LL * K * (N - i);
				ans += A[N - 1];
				return ans;
			}
		}
	}
	return ans;
}

// GRADER DI ESEMPIO, NON MODIFICARE

#ifndef EVAL

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> A(N);
    for (int &a: A) cin >> a;

    cout << carica(N, K, A) << endl;

    return 0;
}

#endif

nel caso di test

5 30
1 2 3 31 32
il risultato dovrebbe essere 69, senza sfrondare alcun tronco, mentre il codice che ho inviato da come risposta 98 e sfronda gli ultimi due tronchi.
Mi spiegate se sto sbagliando qualcosa?

Grazie mille in anticipo!

2

La tua soluzione è effettivamente sbagliata: trova sempre il caso migliore sfrondando sempre almeno un tronco, ti basta confrontare il risultato con il caso in cui non sfrondi alcun tronco.

Comunque mi stupisce il fatto che prenda 100/100 …
Metteremo (eventually) a posto i casi di test

3

Io sono riuscito a risolverlo semplicemente così: con un algoritmo DP. Per darti un suggerimento senza spoilerarti tutto, ragiona su quanto ti costa spostare alberi non sfrondati e farli arrivare a 0, quanto ti costa invece spostarli come singoli sfrondati e quanto come catena.

Alla fine, esce un codice veramente di poche righe e veramente curioso. Sto maledetto problema mi ci ha messo qualche mese per capirlo, perché pensavo veramente fosse un greedy banale, ma quando ho cambiato approccio mi volevo prendere a sberle :rofl: