Pomoc- Menager

Dakle ideja je ovakva:
Radi se dinamicki, sortiramo po krajevima i krenemo od pocetka.
OPT[x] je niz koji oznacava najbolje za prvih x filmova (prvih x mislim kad se sortira po krajevima). Binarnom pretragom nadjem od koliko krajeva do x-tog je veci x-ti pocetak, i onda je
OPT[x]=max{ OPT[x-1], vrednost[x]+OPT[od onoliko filmova od koliko je veci levi kraj x-tog filma}

Koliko ja vidim, ideja je u redu, ako nije ne citaj dalje, nego hvataj tastaturu u ruke i pisi zasto nije dobra.

Takav kod ne prolazi za sest test-primera i sad moguce je da imam gresku u kodu (verovatno kod binarnog pretrazivanja i pamcenja indexa) tako da evo ga kod ako nekog ne mrzi, nek pogleda (lakse ce se snaci oni koji su zadatak resavali sa ovom idejom)


type
TFilm=record
p,k,o:longint;
end;

var
film:array [1..100001] of TFilm;
opt:array [0..100001] of longint;
n, i, j:longint;


procedure qs(l,d:longint);
var
i,j,x:longint;
y:TFilm;
begin
i:=l; j:=d; x:=film[(l+d) div 2].k;
repeat
while film[i].k<x do i:=i+1;
while x<film[j].k do j:=j-1;
if i<=j then begin
y:=film[i]; film[i]:=film[j]; film[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<d then qs(i,d);
if l<j then qs(l,j);
end;


function max(a,b:longint):longint;
begin
max:=a; if a<b then max:=b;
end;


function binTraz(x, ind:longint):longint;
var
l,d,index,sr:longint;
uspeh:boolean;

begin

l:=1; d:=ind;
uspeh:=false;
index:=-1;

repeat

sr:=(l+d) div 2;

if x=film[sr].k then begin
uspeh:=true;
index:=sr
end

else begin
if x>film[sr].k then l:=sr+1
else d:=sr-1
end

until (d<l) or uspeh;

if uspeh then binTraz:=index-1
else binTraz:=d

end;

begin
readln(n);
for i:=1 to n do readln(film[i].p, film[i].k, film[i].o);
fillChar(opt, sizeOf(opt), 0);

qs(1,n);

opt[0]:=0;
opt[1]:=film[1].o;

for i:=2 to n do
opt[i]:=max(opt[binTraz(film[i].p,i)]+film[i].o, opt[i-1]);


writeln(opt[n]);
end.

Pa greska je u tome sto ti prekidas pretragu cim naidjes na prvi element ciji je kraj manji od x..Moze da postoji jos neki interval, desno od nadjenog, ciji kraj takodje ne dolazi do x a cija je optimalna vrednost veca od nadjenog...

Znaci kada naides na neki interval ciji je kraj manji od x a kraj predhodno nadjenog elementa je iza njega ili je kraj predhodnog elementa jednak predhodno pronadjenom a opt[novi]>opt[stari] ,belezis taj element i menjas levo na "mid + 1"...Iz petlje izlazis tek kada levo bude vece od desnog...
Tako sam ja radio...

evo ti kod za binarnu pretragu...Tako je lakse..Sve ostalo ti je ok.

//a-pocetak, b-kraj, w-tvoje x, u-optimalne vrednosti

int search(int a, int b, int w)
{
int dif = w+1, elem=0;
int mid, tmp;
while(a<=b)
{
mid =(a+b)>>1; //(a+b)/2;
tmp = w - f[mid].y;
if(tmp>0)
{
if(dif>tmp || (dif==tmp && u[elem]<u[mid]))
{
dif = tmp;
elem = mid;
}
a = mid+1;
}
else
b = mid-1;
}
return elem;
}

E ima smisla...
Sad cu da probam pa cemo da vidimo :)

Inace ja ne znam C tako da ovaj tvoj kod bas i nije od neke pomoci :)

E kad sam video da su svi test primeri tacni nisam mogao da poverujem

Ne znam samo da li je veca sramota sto sam deset puta slao i nisam primetio gde je greska, ili sto sam slao jos 5 puta sve dok je nisam najzad otklonio :)

pozdrav i hvala

Isto radim zadatak, dinamicki i binary search i ne prolazi ni jedan primer a sve koje sam ja dao i oni dati u zadatku prolaze ... help?

sortuj ih po kraju

sortiram ih po levom kraju , ako su levi krajevi jednaki onda po desnom.

a mozda tebi kraj znaci levi kraj intervala

*** GRESKA *** DESNI KRAJ

Da to je bio problem... RESEN:D 10x a lot