Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2010-12-28 19:18:32

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Лучшие решения задач второго тура

Задача Wie

Код:

function max(a,b:longint):longint;
begin if a>b then max:=a else max:=b;end;
var a:array[0..201,0..201]of longint;
i,j,k,n,minimum:longint;
begin
read(n);
for i:=1 to n do read(a[1,i]);
if n=1 then writeln(a[1,1]) else begin
   for j:=2 to n do
       for i:=1 to (n-j+1) do begin
       minimum:=2000000000;
           for k:=(i+1) to (j+i-1) do begin
           a[j,i]:=max(a[k-i,i],a[i+j-k-1,k+1])+a[1,k];
           if minimum>a[j,i] then minimum:=a[j,i];
           end;
       a[j,i]:=minimum;
       end;
   writeln(a[j,i]);
end;
end.

Поза форумом

 

#2 2010-12-28 20:17:53

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

вот решение moneybox на питоне (на этом сервере не работает, слишком стар питон), которым я проверял сишное решение

inp = map(int,raw_input().split())
N = inp[0]
z = inp[1:N+1]
M = inp[N+1]

x=0L
for i in z:
    x |= 1<<(i-1)

for j in range(1,M):
    y=0L
    for i in z:
        y |= x<<i
    x=y

print bin(x).count("1")

Поза форумом

 

#3 2010-12-28 20:20:45

Depool
Новий користувач
Звідки: Дніпропетровськ
Зареєстрований: 2009-11-29
Повідомлень: 15

Re: Лучшие решения задач второго тура

Wie:

Код:

{$APPTYPE CONSOLE}
var
 o,n,i,j,k:longint;
 b:array[1..200,1..200] of longint;
 a:array[1..200] of longint;

 Function min(a,b:longint):longint;
 begin
  If a<b then min:=a else min:=b;
 end;

 Function max(a,b:longint):longint;
 begin
  If a>b then max:=a else max:=b;
 end;

begin
 read(n);
 For i:=1 to n do read(a[i]);
 For i:=1 to n do b[i,i]:=a[i];
 For i:=2 to n do
  For j:=1 to n-i+1 do
  begin
   b[j,j+i-1]:=1000000000;
   For k:=j to j+i-1 do
   begin
    If k=j then o:=a[k]+b[k+1,j+i-1]
    else if k=j+i-1 then o:=a[k]+b[j,k-1]
    else o:=a[k]+max(b[j,k-1],b[k+1,j+i-1]);
    b[j,j+i-1]:=min(b[j,j+i-1],o);
   end;
  end;
  write(b[1,n]);
end.

Відредаговано Depool (2010-12-28 21:02:28)


Всегда выбирайте самый трудный путь - на нем вы не встретите конкурентов

Поза форумом

 

#4 2010-12-28 20:24:08

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

"Лучшие" - це геніальні, чи просто, які проходять всі тести?

Поза форумом

 

#5 2010-12-28 20:25:20

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

Код:

program Crossing;

uses
  Math;

type
  TPoint = record
    X, Y: Longint;
  end;  
  PArr = ^TArr;
  TArr = record
    L: Longint;
    St, En: array [1..1000] of TPoint;
  end;

var
  LastC, C, I, J, N, K, CurX, CurY, Y1, Y2, YY2, X1, XX1, X2: Longint;
  NapX, NapY, X0, Y0: Shortint;
  A, B: TArr; // A = Gorisontal; B = Vertical;
  Cur: PArr;

begin
  NapX := 1;
  NapY := 0;
  A.L := 0;
  B.L := 0;
  CurX := 0;
  CurY := 0;
  Read(N);
  C := -3;
  for I := 1 to N do
    begin
      LastC := C;
      Read(C);
      case C of
        -1: begin
              X0 := NapX;
              Y0 := NapY;
              NapX := Y0;
              NapY := -X0;
            end;
        -2: begin
              X0 := NapX;
              Y0 := NapY;
              NapX := -Y0;
              NapY := X0;
            end;
        else
            begin
              if NapY = 0
                then Cur := Addr(A)
                else Cur := Addr(B);
              if LastC < 0
                then
                  begin
                    Inc(Cur^.L);
                    Cur^.St[Cur^.L].X := CurX;
                    Cur^.St[Cur^.L].Y := CurY;
                    CurX := CurX + C * NapX;
                    CurY := CurY + C * NapY;
                    Cur^.En[Cur^.L].X := CurX;
                    Cur^.En[Cur^.L].Y := CurY;
                  end
                else
                  begin
                    CurX := CurX + C * NapX;
                    CurY := CurY + C * NapY;
                    Cur^.En[Cur^.L].X := CurX;
                    Cur^.En[Cur^.L].Y := CurY;
                  end;
            end;
      end;
    end;
  K := 0;  
  for I := 1 to A.L do
    for J := 1 to B.L do
      begin
        Y1  := A.St[i].Y;
        X1  := Min(A.St[i].X, A.En[i].X);
        XX1 := Max(A.St[i].X, A.En[i].X);
        X2  := B.St[J].X;
        Y2  := Min(B.St[J].Y, B.En[J].Y);
        YY2 := Max(B.St[J].Y, B.En[J].Y);
        if (X1 < X2) and (X2 < XX1) and (Y2 < Y1) and (Y1 < YY2) then
          Inc(K)
      end;    

  Writeln(K);
end.

Код:

program Derivative;

uses
  Math;

const
  Zero = Ord('0');
  Arr: array [False..True, '0'..'9'] of Longint =
       ((0, 1, 8, 27, 64, 125, 216, 343, 512, 729),
        (0, 1, 4,  9, 16,  25,  36,  49,  64,  81));

var
  I, J, K, NNN, P2, D: Longint;
  Par: Boolean;
  P, P1: Int64;
  S: String;
  Z: Char;
  A: array [1..1020] of Longint;

begin
  Read(P, K);

  I := 1;
  while I <= K do
    begin
      P1 := 0;
      Par := False;
      Str(P, S);
      for J := 1 to Length(S) do
        begin
          Z := S[J];
          Inc(P1, Arr[Par, Z]);
          Par := not Par;
        end;
      P := P1;
      if I <= 1020 then
        begin
          A[i] := P;
          for J := 1 to I - 1 do
            if A[J] = P then
              begin
                D := I - J;
                K := I + (K - I) mod D;
                Break;
              end;
        end;
      Inc(I);
    end;
  Writeln(P);
end.

Код:

program Krizis;

uses
  Math;

var
  I, J, L, N, K, T, P: Longint;
  A: array [1..100] of Longint;

begin
  Read(L, N);
  for I := 1 to N do Read(A[i]);
  for I := 1 to N - 1 do
    for J := I to N do
      if A[i] > A[J] then
        begin
          T := A[i];
          A[i] := A[J];
          A[J] := T;
        end;

  L := L + L;
  K := 1;
  P := A[1];
  for I := 2 to N do
    if A[i] - P > L then
      begin
        Inc(K);
        P := A[i]; 
      end;

  Writeln(K);
end.

Код:

program MoneyBox;

uses
  Math;
  
type
  PArr = ^TArr;
  TArr = array [0..11000] of Longint;

var
  N, M, Step, I, J, NMin: Longint;
  A: array [1..7] of Longint;
  NewB: PArr; // Linker on position in massive Old
  OldA, NewA: PArr; // Lists of current values
  LastOldA, LastNewA: PArr; // Lists of last monet

begin
  New(NewA);
  New(NewB);
  New(LastNewA);
  FillChar(LastNewA^, SizeOf(LastNewA^), 0);
  FillChar(NewA^, SizeOf(NewA^), 0);
  Read(N);

  NewA^[0] := N;
  for I := 1 to N do Read(A[i]);
  for I := 1 to N - 1 do
    for J := I + 1 to N do
      if A[i] > A[J] then
        begin
          M := A[J];
          A[J] := A[i];
          A[i] := M;
        end;
  Read(M);
  if (A[1] = 1) and (A[2] = 100)
    then NMIn := 103
    else NMIn := 55;

  for I := 1 to N do
    begin
      NewA^[i] := A[i];
      LastNewA^[i] := I;
    end;

  for Step := 2 to Min(NMin, M) do
    begin
      OldA := NewA;
      FillChar(NewB^, SizeOf(NewB^), 0);
      LastOldA := LastNewA;
      New(NewA);
      New(LastNewA);
      FillChar(NewA^, SizeOf(NewA^), 0);
      FillChar(LastNewA^, SizeOf(LastNewA^), 0);
      NewA^[0] := 0;
      LastNewA^[0] := 0;
      for I := 1 to OldA^[0] do
        for J := LastOldA^[i] to N do
          begin
            if NewB^[OldA^[i] + A[J]] = 0 then
              begin
                Inc(NewA^[0]);
                NewB^[OldA^[i] + A[J]] := NewA^[0];
                NewA^[NewA^[0]] := OldA^[i] + A[J];
                LastNewA^[NewA^[0]] := J;
              end;
          end;
    end;
  if M > NMin then
    begin
      OldA := NewA;
      FillChar(NewB^, SizeOf(NewB^), 0);
      LastOldA := LastNewA;
      New(NewA);
      New(LastNewA);
      FillChar(NewA^, SizeOf(NewA^), 0);
      FillChar(LastNewA^, SizeOf(LastNewA^), 0);
      NewA^[0] := 0;
      LastNewA^[0] := 0;
      for I := 1 to OldA^[0] do
        for J := LastOldA^[i] to N do
          begin
            if NewB^[OldA^[i] + A[J]] = 0 then
              begin
                Inc(NewA^[0]);
                NewB^[OldA^[i] + A[J]] := NewA^[0];
                NewA^[NewA^[0]] := OldA^[i] + A[J];
                LastNewA^[NewA^[0]] := J;
              end;
          end;
      NewA^[0] := (NewA^[0] - OldA^[0]) * (M - NMin - 1) + NewA^[0];  
    end;
  Writeln(NewA^[0]);
end.

Код:

program Wie;

uses
  Math;

var
  I, J, Z, N, K, MinZ: Longint;
  A: array [1..200, 1..200] of Longint;

begin
  Read(N);
  Read(A[1, 1]);
  K := 2;
  for I := K to N do
    begin
      Read(A[1, I]);
      A[K, I] := A[K-1, I-1] + A[K-1, I];
    end;
  Inc(K);  // 3
  for I := K to N do
    A[K, I] := Max(A[K-1, I-1], A[K-1, I]);

  for K := 4 to N do
    begin
      for I := K to N do
        begin
          MinZ := 1000000000;
          for J := 2 to K - 1 do
            begin
              Z := A[1, I-K+J] + Max(A[J-1, I-K+J-1], A[K-J, I]);
              if MinZ > Z then MinZ := Z;
            end;
          A[K, I] := MinZ;  
        end;
    end;

  Writeln(A[N, N]);
end.

Це всі 40-ка бальні

Add: Пояснення до задач "простими словами"

Відредаговано MItornaDOS (2010-12-29 09:39:32)

Поза форумом

 

#6 2010-12-28 20:34:12

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

MItornaDOS написав:

"Лучшие" - це геніальні, чи просто, які проходять всі тести?

Я думаю проходять всі тести і дуже швидко)

Поза форумом

 

#7 2010-12-28 20:57:40

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

LeonID написав:

Наприклад в цій яка бере 100% ніякої ідеї я не знайшов(тільки труднощі)

Це яка?

Поза форумом

 

#8 2010-12-28 20:58:11

Depool
Новий користувач
Звідки: Дніпропетровськ
Зареєстрований: 2009-11-29
Повідомлень: 15

Re: Лучшие решения задач второго тура

LeonID, я думаю, будь-який 40-ка бальный розв'язок задачі Crossing буде некороткий і нагромаджений різними умовами, які не дуже приємно розбирати.

Відредаговано Depool (2010-12-28 20:59:44)


Всегда выбирайте самый трудный путь - на нем вы не встретите конкурентов

Поза форумом

 

#9 2010-12-28 21:11:40

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

LeonID написав:

MItornaDOS написав:

"Лучшие" - це геніальні, чи просто, які проходять всі тести?

По-перше це короткі програми(за що я ненавиджу С, С++), по друге в них чітко видно основну ідею. Наприклад в цій яка бере 100% ніякої ідеї я не знайшов(тільки труднощі)
ЗАДАЧА CROSSING

Код:

var dx,dy:integer;
procedure napramvlivo(a,b:integer);

в этом примере главное - владение украинским языком. вліво-вправо вместо ліворуч-праворуч

Поза форумом

 

#10 2010-12-28 21:17:45

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

вот быстрое грязное решение derivative (которое понимает позицию в авторском смысле)

Код:

#include <cstdlib>
#include <iostream>
using namespace std;

int f( long x) {
    int p, rz, d, t, rz1;
    p=rz=rz1=0;

    while (x) {
        d = x%10;
        t = d*d;
        
        if (p) {
            rz += t*d;
            rz1 += t;
        } else {
            rz += t;
            rz1 += t*d;
        }

        x /= 10;
        p ^= 1;
    }

    if (p) {
        rz = rz1;
    }

    return rz;
}

int main(int argc, char** argv) {
    long P, k;
    cin >> P >> k;

    do {
        if ((P==1)||(P==24)||(P==135)||(P==175)||(P==407)||
                (P==225)||(P==134)||(P==343)||(P==344)) {
            break;
        }
        P = f(P);
    } while (--k);

    int rz;
    if (!k||(P==1)||(P==24)||(P==135)||(P==175)||(P==407)) {
        rz = P;
    } else {
        if (P==225) {
            int period[13] = {225,137,353,79,424,132,18,65,241,25,33,36,63};
            rz = period[k%13];
        } else if (P==134) {
            int period[11] = {134,74,359,781,408,576,390,108,513,153,53};
            rz = period[k%11];
        } else if (P==343) {
            int period[2] = {343,70};
            rz = period[k%2];
        } else {
            int period[2] = {344,107};
            rz = period[k%2];
        }
    }

    cout << rz << endl;
    return 0;
}

Поза форумом

 

#11 2010-12-29 09:36:27

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

Пояснення до 40-ка бальних задач з коммента #5

Crossing
Виконуємо всі команди, формуємо 2 масиви - горизонтальні і вертикальні відрізки, які проходив робот
В кінці перевіряємо кількість перетинів цих горизонтальних і вертикальних відрізків.
Не забуваємо, що якщо робот пройшов певну відстань, а потім, не змінюючи напрямку руху, пройшов знову відстань, то ці два однонапрямлені відрізки потрібно об'єднати і вважати як один

Derivative
Беремо знаходимо похідні і заносимо їх до масиву до тих пір, поки не побачимо, що деяку похідну ми вже зустрічали (для цього нам і масив потрібний)
Знаходимо період і, враховуючи період похідної, знаходимо шукане значення

Krizis
Тут - банальна динаміка
Знаходимо різниці між кожними двома сусідніми рахунками, заносимо це в масив
Далі з початку до кінця ці всі різниці ділимо на групи так, щоб сума цих всіх різниць не була більша за 2*L
Кількість груп - це і є відповідь

MoneyBox
Якщо M > 50 то рахуємо до 50 всі можливі суми в масиві.
А далі виходить дуже цікаво:
Якщо A[i] - це кількість можливих сум після i витягань, то для всіх i > 50
A[i+1] - A[i] = const
Цим користуємось, щоб не злетіти в часі на гіганських тестах

Wie
У цій задачі рекурсія = утопія, це зрозуміло, тому я використовував повний перебір варіантів динамікою.
Спочатку ділимо всі відрізки на групи по 2 відрізки, знаходимо мінімальний час для них (це вийде сума)
Потім ділимо всі відрізки на групи по 3 відрізки, знаходимо мінімальний час для них (це вийде середній елемент + більший з двох крайніх)
Потім ділимо всі відрізки на групи по 4 відрізки, знаходимо мінімальний час для них
etc

Якщо є питання - звертайтесь.

Відредаговано MItornaDOS (2010-12-29 09:40:14)

Поза форумом

 

#12 2010-12-29 10:57:01

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

В задачі MoneyBox необхідно використати зливання масивів. Знайти всі можливі варіанти можна за алгоритмом який виклали тут http://www.cyberforum.ru/cpp-beginners/ … 04690.html
(знайшов уже після того як розвязав сам. MItornaDOS це не Ви його виклали?). А вже потім потрібно шукати період на яку збільшуються суми. (Друга задача на пошук періоду)

Поза форумом

 

#13 2010-12-29 11:13:59

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

Задача MoneyBox

Код:

type
br=array[1..10000]of integer;
var z,z1,z2:br;
function mergelenZ(a,b:br;len:longint):integer;
var i,j,k:integer;
begin
i:=1;j:=1;k:=0;
while(j<=len)do begin
        if (a[i]<b[j])and(a[i]<>0) then begin
        k:=k+1;
        z2[k]:=a[i];
        i:=i+1;
        end
        else
        if a[i]=b[j] then begin
        k:=k+1;
        z2[k]:=a[i];
        i:=i+1;
        j:=j+1;
        end
        else begin
        k:=k+1;
        z2[k]:=b[j];
        j:=j+1;
        end;
end;
mergelenZ:=k;
end;
var
vidpovid:longint;
aa,null:br;
k,i,m,leng,leng1,p,j,t:longint;
delta:array[0..200]of integer;
begin
for i:=1 to 10000 do begin
aa[i]:=0;null[i]:=0;z[i]:=0;z1[i]:=0;z2[i]:=0;
end;
read(k);
for i:=1 to k do read(z[i]);leng1:=k;
read(m);
for i:=1 to k do
   for j:=k downto i do
      if z[i]>z[j] then begin
         t:=z[i];
         z[i]:=z[j];
         z[j]:=t;
         end;
         z1:=z;
for i:=1 to m-1 do begin
        for j:=1 to k do begin
                for p:=1 to leng1 do begin
                aa[p]:=z[j]+z1[p];
                end;
        leng:=mergelenZ(z2,aa,leng1);
        end;
        z1:=z2;
        z2:=null;
        delta[i]:=leng-leng1;
     leng1:=leng;
     if (i>2) then
        if (delta[i]=delta[i-1])and(delta[i]=delta[i-2])then break;
end;
vidpovid:=leng1+(m-i-1)*delta[i];
writeln(vidpovid);
end.

Поза форумом

 

#14 2010-12-29 11:22:43

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

На тому форумі ніколи не був. Що значить "зливання масивів"?

Поза форумом

 

#15 2010-12-29 11:36:04

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

Теж саме що обєднання множин.

Поза форумом

 

#16 2010-12-29 11:44:37

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

Я маю на увазі яку роль воно грає?

Поза форумом

 

#17 2010-12-29 11:59:39

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Лучшие решения задач второго тура

Припустимо у вас є N-монет, тоді після витягнення наступної монети у вас буде множина з N сум, але деякі суми можуть бути однакові, отже різна кількість = обєднанню множин

Поза форумом

 

#18 2010-12-29 12:05:41

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

А-а-а, це як елемент підрахунку кількості можливих сум для невеликих M smile
От що мене більше цікавить – це те, від чого і як залежить кількість витягань Mmin після яких для даних номіналів з'являється властивість описана вище:

Якщо A[i] - це кількість можливих сум після i витягань, то для всіх i > 50
A[i+1] - A[i] = const

Поза форумом

 

#19 2010-12-29 12:56:35

Гожий
Новий користувач
Зареєстрований: 2010-12-15
Повідомлень: 14

Re: Лучшие решения задач второго тура

Спочатку мені ця задача (WIE) нагадала досить швидкий пошук елемента у масиві: масив спочатку впорядковується по спаданню, далі дивимось на середній елемент:
1) він може бути шуканим елементом, тоді робимо, що просять;
2) він може бути більшим за шуканий елемент, тоді повторюємо операцію для відрізку, що залишився справа;
3) він може бути меншим за шуканий елемент, тоді повторюємо операцію для відрізку, що залишився зліва.
Задача з туру - аналогічна, на мою думку. В чому хибність думки?

Поза форумом

 

#20 2010-12-29 12:59:37

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

Щось я взагалі не зрозумів ідеї... Яке це має відношення до задачі? Хто дозволяв впорядковувати елементи і взагалі міняти їх місцями? Скільки балів набирає такий розв'язок?

Поза форумом

 

#21 2010-12-29 13:19:12

Гожий
Новий користувач
Зареєстрований: 2010-12-15
Повідомлень: 14

Re: Лучшие решения задач второго тура

У задачі ''WIE'' масив рахується вже впорядкованим, адже знайти треба межу (елемент, у вище описаній), з одного боку межі нафта є (з лівого), з іншого не має (відрізок, де є нафта не розкиданий по АВ).
Або інакше: ми свердлимо середній пункт, якщо нафта там є, то межа буде десь в правому відрізку, і навпаки..

Поза форумом

 

#22 2010-12-29 14:37:44

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Лучшие решения задач второго тура

ну... тільки тут інколи треба зміщуватись в певний бік, наприклад на тесті 9 1 2 3 4 5 6 7 8 9 варто сверлити спочатку не "5" а "6"
От діло в тому, що потрібно знайти, що перше потрібно сверлити, а потім друге, третє і т.д.

Поза форумом

 

#23 2010-12-29 16:18:40

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Лучшие решения задач второго тура

Скажу чесно: конкретно задачу WIE я вкрав готову (тільки не скажу звідки wink )

Найкращий розв'язок на тому сайті, звідки я її вкрав, такий (прізвище автора розв'язку -- Андрихович)

Код:

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i,n) for (int i=0; i<(n); ++i)
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define FORE(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define CLR(x) memset(x,0,sizeof x)
#define xx first
#define yy second
typedef long long int lli;
typedef pair<int, int> P;
typedef vector<int> vi;


using namespace std;
#define MAXN 2007
#define INF 100000000
int n,t[MAXN],dp[MAXN][MAXN]={0},prawog[MAXN]={0},lewog[MAXN]={0};
deque<P> prawo[MAXN],lewo[MAXN];

void dodaj(deque<P>& q,P p){
        while(!q.empty() && q.back().yy >= p.yy) q.pop_back();
        q.PB(p);
}

int nast(deque<P>& q){
        P x=q.front();
        q.pop_front();
        if(q.empty()) return INF;
        P res=q.front();
        q.push_front(x);
        return res.yy;
}

void go(int l,int r){
//        cout << "op " << prawo[l].front().xx << "/" << prawo[l].front().yy << endl;
//        cout << "op " << lewo[r].front().xx << "/" << lewo[r].front().yy << endl;
        while(prawo[l].front().xx + lewo[r].front().xx < r-l){
                if(nast(prawo[l]) < nast(lewo[r])) prawo[l].pop_front();
                else lewo[r].pop_front();
        }
        dp[l][r]=max(prawo[l].front().yy, lewo[r].front().yy);
//        cout << "go " << l << " " << r << " " << dp[l][r] << endl;
        dodaj(prawo[l], P(r-l+1, dp[l][r]+t[r+1]));
        dodaj( lewo[r], P(r-l+1, dp[l][r]+t[l-1]));
}

int main(){
        //in
        scanf("%d",&n);
        FOR(i,1,n) scanf("%d",&t[i]);
        //rozw
        FOR(i,1,n) {
                prawo[i].PB(P(0,t[i]));
                lewo[i].PB(P(0,t[i]));
        }
        REP(d,n) FOR(i,1,n-d) go(i,i+d);
        //out
        printf("%d\n",dp[1][n]);
        return 0;
}

На розмірах значно більших 200 (наприклад, 2000) працює значно швидше.
Щоправда, я сам не дуже розумію, як той розв'язок працює, тому в нас обмеження було 200.

Відредаговано Ilya Porublyov (2010-12-29 16:19:28)

Поза форумом

 

#24 2010-12-29 20:17:15

Olesuk
Новий користувач
Зареєстрований: 2010-10-31
Повідомлень: 9

Re: Лучшие решения задач второго тура

Ілля Миколайовичу, а можете розказати саму ідею розвязку і її складність(бо з цього коду мені нічого не зрозуіло).
І ще, а які обмеження по пам'яті і часу має ця задача на 2-ох тисячах точок.

Поза форумом

 

#25 2010-12-29 20:24:04

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

Ilya Porublyov написав:

Скажу чесно: конкретно задачу WIE я вкрав

и правильно сделали - ведь просто задача это одно, а задача о том, как правильно добыть сотни-две нефти несет несомненную практическую пользу

п/с/ Marcin Andrychowicz ? вон сколько медалей

Відредаговано Иванов (2010-12-29 20:26:55)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt