Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.05.2008, 01:33
гость

 
Сообщений: n/a

Лесенка-2
Решаю задачу вроде простая, но что то не проходит пишет WR5 даже не предполагаю что тут не правильно
вот задача
Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Также он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошел Вова.

Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество ступеней лестницы. Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Количество ступеней не превышает 1000, числа, написанные на ступенях, не превосходят по модулю 1000.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать в первой строке наибольшее значение суммы. Во второй строке должны быть записаны через пробел номера ступеней по возрастанию, по которым должен шагать Вова.
INPUT.TXT
3
1 2 1
---
3
1 –1 1
OUTPUT.TXT
4
1 2 3
---
2
1 3

вот ссылка
http://acm.dvpion.ru/?main=task&id_task=329
я решал так
readln(n);
for i:=1 to n do read(a[i]);
sum[0]:=inf;sum[1]:=a[1];
a[0]:=inf;
for i:=2 to n do begin
sum[i]:=max(sum[i-1],sum[i-2])+a[i];
end;
writeln(sum[n]);
потом идёт вывод путитоже циклом обратным проходом по массивы sum
но что то тут не правильно в чём ошибка не знаю(
  #2  
Старый 08.05.2008, 08:39
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Это одна из самых простых задач на дин. программирование.
В примере приведено медленное рекурсивное решение и преобразование в дин.прогр. Путь собирается достаточно тупо, можно оптимизировать

Код:
procedure TForm3.Button7Click(Sender: TObject);
var
  St: array of Integer;
  i, Len: Integer;
  s: string;

  function SMax(k: Integer): Integer;
  begin
    if k < 1 then
      Result := 0
    else
      Result := St[k] + Max(Smax(k - 1), SMax(k - 2));
  end;

  function DinMax(k: Integer; var Path: string): Integer;
  var
    i: Integer;
    Sum, L: array of Integer;
  begin
    SetLength(Sum, k + 2);
    SetLength(L, k + 2);
    Sum[0] := 0;
    Sum[1] := 0;
    for i := 2 to k + 1 do begin
      if Sum[i - 1] >= Sum[i - 2] then begin
        Sum[i] := Sum[i - 1] + St[i - 1];
        L[i] := 1;
      end
      else begin
        Sum[i] := Sum[i - 2] + St[i - 1];
        L[i] := 2;
      end;
    end;
    Path := IntToStr(k);
    i := k + 1 - L[k + 1];
    while i > 1 do begin
      Path := IntToStr(i - 1) + ' ' + Path;
      i := i - L[i];
    end;
    Result := Sum[k + 1];
  end;

begin
  Memo1.Clear;
  Randomize;
  Len := 5 + Random(12);
  SetLength(St, Len + 1);
  for i := 1 to Len do begin
    St[i] := Random(20) - 8;
    Memo1.Lines.Add(Format('%d:    %d ',[i, St[i]]));
  end;
  Memo1.Lines.Add('------');
  Memo1.Lines.Add(Format('%d   %d', [SMax(Len), DinMax(Len, s)]));
  Memo1.Lines.Add('Path: '+ s);
end;
  #3  
Старый 17.05.2010, 21:47
гость

 
Сообщений: n/a

я тоже решаю и не понятно почему ВА5
program Lesenka;

{$APPTYPE CONSOLE}

const nmax=1000;
var
a:array[1..nmax] of integer;
s:array[0..nmax] of string;
s1:string;
n,i:integer;
sum:array[0..nmax] of integer;
Function max(a,b:integer):integer;
begin
If a>=b then max:=a else max:=b;
end;
begin
Assign(Input,'Input.txt');
reset(input);
Assign(output,'Output.txt');
rewrite(output);
read(n);
Fillchar(a,sizeof(a),0);
Fillchar(sum,sizeof(sum),0);
For i:=1 to n do read(a[i]);
sum[1]:=a[1];
str(1,s1);
s[1]:=s[1]+s1;
sum[0]:=0;
For i:=2 to n do
begin
sum[i]:=max(sum[i-1],sum[i-2])+a[i];
str(i,s1);
If max(sum[i-1],sum[i-2])=sum[i-1] then s[i]:=s[i-1]+s1
else s[i]:=s[i-2]+s1;
end;
writeln(sum[n]);
S1:=S[N];
For i:=1 to length(s[n]) do write(s[n][i],' ');
end.
  #4  
Старый 09.11.2010, 22:26
Новичок

Отправить личное сообщение для хус++ Посмотреть профиль Найти все сообщения от хус++
 
Регистрация: 09.11.2010
Сообщений: 7

вот мое решение на си++
#include <string.h>
#include <stdio.h>
long a[2000], i, n, b[2000], c[2000];
long max(long a,long b)
{
if(a>b)return a;
return b;
}
int main()
{
freopen("INPUT.TXT","r",stdin);
freopen("OUTPUT.TXT","w",stdout);
scanf("%li",&n);
for(i=2;i<n+2;i++){c[i]=0;scanf("%li",&a[i]);if(a[i]>=0)c[i]=1;}
for(i=2;i<n+2;i++)
{
b[i]=max(b[i-1],b[i-2])+a[i];
}
printf("%li\n",b[n+1]);
for(i=n+1;i>=2;i--)
{
if(b[i]==b[i-1]+a[i]){c[i-1]=1;continue;}
else {if(b[i]==b[i-2]+a[i]){c[i-2]=1;i--;continue;}}
}
c[n+1]=1;
for(i=2;i<n+2;i++)
{
if(c[i]==1)printf("%li ",i-1);
}
return 0;
}
  #5  
Старый 31.01.2011, 17:44
Новичок

Отправить личное сообщение для Templar Посмотреть профиль Найти все сообщения от Templar
 
Регистрация: 29.01.2011
Сообщений: 3

Сообщение от хус++ Посмотреть сообщение
вот мое решение на си++
#include <string.h>
#include <stdio.h>
long a[2000], i, n, b[2000], c[2000];
long max(long a,long b)
{
if(a>b)return a;
return b;
}
int main()
{
freopen("INPUT.TXT","r",stdin);
freopen("OUTPUT.TXT","w",stdout);
scanf("%li",&n);
for(i=2;i<n+2;i++){c[i]=0;scanf("%li",&a[i]);if(a[i]>=0)c[i]=1;}
for(i=2;i<n+2;i++)
{
b[i]=max(b[i-1],b[i-2])+a[i];
}
printf("%li\n",b[n+1]);
for(i=n+1;i>=2;i--)
{
if(b[i]==b[i-1]+a[i]){c[i-1]=1;continue;}
else {if(b[i]==b[i-2]+a[i]){c[i-2]=1;i--;continue;}}
}
c[n+1]=1;
for(i=2;i<n+2;i++)
{
if(c[i]==1)printf("%li ",i-1);
}
return 0;
}
А теперь можно то-же самое только с пояснениями и комментами?

типа что ты хранишь в какой переменной и если можно ссылку на разбор.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра