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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.09.2010, 07:26
Новичок

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

Динамическое программирование
Здравствуйте люди !!! Сейчас я начал изучать ДП и мне почти на каждой задаче нужна помощь. Каждый раз создавать новый раздел не удобно.
  #2  
Старый 09.09.2010, 07:29
Новичок

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

Вот одна из тех задач. Первую я решил,а с остальными задачами проблемы . Если кто-то знает как решаются остальные задачи, прощу объяснить
  #3  
Старый 09.09.2010, 07:48
MBo MBo вне форума
Местный

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

На беглый взгляд, задачи D и С - самые простые. Попробуй для начала для них что-то сам придумать.
А заниматься разъяснением с нуля десятка задач вряд ли кому интересно...

Кстати, здесь набор задач с решениями:
http://algolist.ru/olimp/
  #4  
Старый 09.09.2010, 12:32
Новичок

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

Да, они легкие. Но вот задача H меня мучает уже приблизительно месяц. Как там в разборе сказано, всё сделал.
Вот код:
Код:
const inf=maxlongint;
const inf1='123';
var
a:array[0..80,0..80] of string;
n,m,i,j,a1,a2:longint;
s,t:string;
ch:char;

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

 function len(i,j:longint):longint;
  begin
   if a[i,j]=inf1 then len:=inf else len:=length(a[i,j]);
  end;

begin
   assign(input,'input.txt'); reset(input);
   assign(output,'output.txt'); rewrite(output);
   n:=0; m:=0; s:=''; t:='';
     while not eoln do
      begin
       read(ch);
       if (ch in['A'..'Z'])or(ch in['a'..'z'])or(ch in['?','*']) then 
        begin
         inc(n); s:=s+ch;
        end;
      end;  readln;
     while not eoln do
      begin
       read(ch);
       if (ch in['A'..'Z'])or(ch in['a'..'z'])or(ch in['?','*']) then 
        begin
         inc(m); t:=t+ch;
        end;
      end;  
//    read(s); n:=length(s); 
//    read(t); m:=length(t);
    a[0,0]:=''; a[0,1]:=''; a[1,0]:='';
    for i:=2 to max(n,m) do begin a[i,0]:=inf1; a[0,i]:=inf1; end;
     for i:=1 to n do 
      begin
       for j:=1 to m do 
        begin
        
         if (s[i]='*')and(t[j]='*') then 
          begin
           a1:=len(i,j-1);
           a2:=len(i-1,j);
           if (a1<a2) then a[i,j]:=a[i,j-1] else a[i,j]:=a[i-1,j];
          end else

         if (s[i]='*')or(t[j]='*') then 
          begin
           ch:=s[i];
           if (ch='*')or(ch='?') then ch:=t[j];
           if (ch='*')or(ch='?') then ch:='A';
           a1:=len(i-1,j);
           a2:=len(i,j-1);
           if a1<a2 then a[i,j]:=a[i-1,j]+ch else
             begin
              a[i,j]:=a[i,j-1];
              if (a[i,j][length(a[i,j])]<>ch)and(a[i,j]<>inf1) then a[i,j]:=a[i,j]+ch;
             end;
          end else

         if ((s[i]=t[j])or(s[i]='?')or(t[j]='?')) then 
          begin
           ch:=s[i];
           if ch='?' then ch:=t[j];
           if ch='?' then ch:='A';
           a[i,j]:=a[i-1,j-1]+ch;
          end else a[i,j]:=inf1;

        end;
      end;
   if a[n,m]=inf1 then writeln('No solution!') else writeln(a[n,m]);
 close(input); close(output);
end.
ВА.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Динамическое программирование(задача) jura Решение задач с acm.sgu.ru 1 03.03.2010 03:01
динамическое программирование гость Задачи 8 12.03.2009 18:49
динамическое программирование. Артур Поиск и обсуждение книг/сайтов 9 19.01.2009 00:18
Задача на динамическое программирование Fedorenko Математические алгоритмы 4 30.06.2007 10:11
динамическое программирование по профилю artie Задачи 6 11.01.2007 18:01