Динамическое программирование! ?

← →
Chuha (2003-10-29 10:10) [0]

Вопрос такой!
Есть задача
Интервал от 0 до 1000000000 выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы
которого задаются, меняются на противоположный (белый на черный, черный на белый).
Так вот помогите мне, как представить эти данные, в массив не умещается. Объясните пожалуйста, желательное с показательными приерами, чтобы было понятней. Спасибо в любом случае!

← →
Anatoly Podgoretsky © (2003-10-29 10:37) [1]

А теперь попонятнее и с подробностями. Без загадок.

← →
Nikolay M. © (2003-10-29 10:57) [2]

> в массив не умещается

Это как?
Делаешь тип - отрезок:
type TSegment = record a, b : integer; end;Потом объявляешь массив отрезков
var segments : array of TSegment;Задаешь его длину (N = числу операций = числу отрезков?)
SetLength (segments, N);И заполняешь его данными:
segments[0].a := 1; segments[0].b := 2; ... segments[N - 1].a := 10; segments[N - 1].b := 20;
Что тут может куда не помещаться?

← →
Chuha (2003-10-29 11:06) [3]

>А теперь попонятнее и с подробностями. Без загадок.
Ну тогда проще с чего начинать решать :)
2Nikolay M.
Спасибо :)

← →
Slym © (2003-10-29 12:13) [4]

Базара нет 1000000000 - большой массив (байтов)
примерно 1Гигабайт (3fffffff) (в свап?)
а в битах 7fffff - 128 Мб - уже реальней

попробуй
сделать так

function GetBit(pBits:pointer;BitsOffset:Int64):boolean;
var
ByteOffset,BitOffset:integer;
b:PByte;
begin
ByteOffset:=BitsOffset div 8;
BitOffset:=BitsOffset mod 8;
b:=PByte(integer(pBits)+ByteOffset);
result:=(b^ and (1 shl (8-BitOffset)))>0;
end;

procedure SetBit(pBits:pointer;BitsOffset:Int64;Value:boolean);
var
ByteOffset,BitOffset:integer;
b:PByte;
begin
ByteOffset:=BitsOffset div 8;
BitOffset:=BitsOffset mod 8;
if Value then
b:=PByte(integer(pBits)+ByteOffset);
b^:=b^ and (not (1 shl (8-BitOffset)));
if Value then
b^:=b^ or (1 shl (8-BitOffset));
end;

var
interval:pointer;
begin
GetMem(interval,$7fffff);
FillChar(interval^,$7fffff,$ff);

SetBit(interval,1234567,true);//что значит покрасить 1234567 в белый
SetBit(interval,7654321,false);//покрасить в черный

FreeMem(interval,$7fffff);
end;

Анатолий правильно сказал. Повторяю: "Дайте нормальное четкое условие задачи".

> Так вот помогите мне, как представить эти данные, в массив
> не умещается

Как это не умещается??? Очень даже умещается в массив из TPoint которые указывают начальную и конечную координаты перекрашиваемых точек

Динамическое программирование! ? Найти похожие ветки