Aiuto per Sushi bar (unimi_sushi)

Aiuto
1

Ciao raga, ho bisogno di aiuto per risolvere il problema Sushi bar.
il mio codice ha problemi per la ricerba binaria: leggendo l intervallo i, vedo l ultimo intervallo j < i tale che la fine di j >= inizio di i, ma non so perchè non riesco.
Ecco il mio codice:

        #include <bits/stdc++.h>
		using namespace std;
		struct piatto{
			int s;
			int e;
			int w;
	};
		int main(){
			int N;
			cin >> N;
			vector<piatto>V(N+1);
			V[0]={-1, -1, 0};
			for(int i = 1; i <= N; i++){
				int S, W, D;
				cin >> S >> W >> D;
				V[i]={S, D + S, W};
			}
			sort(V.begin(), V.end(), [](const piatto a, const piatto b){
				return a.e < b.e;
			});
			vector<int>DP(N + 1, 0);
			for(int i = 1; i <= N; i++){
				auto it = upper_bound(V.begin(), V.begin() + i, V[i].s, [](const int v, const  piatto a){
					return a.e <= v;
				});
				//primo elemento con a.e > v[i].s
		
				int idx = it - V.begin();
				idx--;
			//	cout << "\t " << V[i].s << " " << V[i].e << " " << V[i].w <<"idx: "<<idx <<endl;
				DP[i] = max(DP[i-1], DP[idx+1] + V[i].w);
		
			
				
			}
			int ret = *max_element(DP.begin(), DP.end());
			cout << ret << endl;
		}

Grazie mille in anticipo!

1 Mi Piace
2

La tua soluzione è corretta ma hai invertito l’operatore nel lower bound. Stando alla reference di C++:

Binary function that accepts two arguments (the first is always val, and the second of the type pointed by ForwardIterator), and returns a value convertible to bool . The value returned indicates whether the first argument is considered to go before the second.

quindi dovresti scrivere return a.e > v;

C’è anche un altro piccolo errore: dopo che fai idx--;, idx ti indica la posizione del piatto che puoi prendere che finisci di mangiare più tardi possibile, quindi non devi poi fare idx + 1 guardi il valore della dp, ma semplicemente DP[i] = max(DP[i - 1], DP[idx] + V[i].w);.

1 Mi Piace
3

grazie mille, troppo forte :slight_smile:

1 Mi Piace