Текст на заборе.

Что-то никак не пойму, как это решается? Поэтому приведу текст задачи полностью.

Цитата

Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "I", "N", "W".

Некто строит незамкнутый забор длиной N досок. Имеются доски, на каждой из которых написана одна из букв "I", "N" или "W". Получившийся забор будет содержать надпись из вышеназванных букв. За каждое нежелательное слово, образуемое какими-либо последовательно стоящими буквами (при прочтении слева направо), придется заплатить штраф, причем столько раз, сколько раз оно встречается на заборе.

Например, если запрещенными словами являются IN - штраф 1 рубль и WIWI - штраф 100 рублей, то за построение забора WIWIWINI будет назначен штраф 201 рубль.

Требуется написать программу определения такой последовательности досок в заборе, для которой штраф минимален.

Ограничения
Штрафы выражаются в рублях Речуйска и представляются целыми числами от 1 до 100.
Количество запрещенных слов <= 50.
Длины запрещенных слов <= 6 символов.

Входные данные
Первая строка файла входных данных INPUT.TXT содержит длину забора N, вторая - количество слов в списке мэра M. В каждой из последующих M строк записано нежелательное слово и через пробел - соответствующий штраф. Все слова попарно различны, состоят только из больших букв латинского алфавита "I", "N" или "W".

Входные данные корректны.

Выходные данные
Результат работы программы выводится в файл OUTPUT.TXT. Первая строка выходного файла должна содержать значение минимального штрафа, а вторая - последовательность из N букв, задающую один из возможных способов построения забора с минимальным штрафом.

Пример:

Цитата

[Входные данные]
8
8
W 10
I 10
N 30
WI 1
WW 10
II 11
WIW 2
IWI 3


[Результат]
98
IWIWIWIW

Честно, кроме полного перебора ничего не придумал

 Первое, что заметил, это неправильная постановка задачи.
 Необходимо указать количества досок с каждой буквой. А то ответ напрашивается сам собой - взять буквы из слова за которое дается наименьший штраф!!!

Не совсем! Более дорогое слово может состоять из нескольких "самых дешевых".
Алгоритм решения очень прост, поэтому подсказывать не буду: думайте сами. ;D

Найти наименьшее общее кратное длинн слов, расширить все слова путем их повторения, посчитать штрафы новых слов, и взять из слова, с наименьшим штрафом, нужное кол-во букв? Больше ничего не придумал.
Блин, ну я и тупой.

насколько я помню задача динамического програмирования

После полного перебора самое простое решение:
инициализируем одной буквой весь забор, считаем полную стоимость, принимаем ее за минимальную.
Ставим указатель на последнюю доску и входим в цикл.
1) Проверяем последня ли доска, если последняя, то сравнение штрафов и в случае успеха сохранение нового рекорда.
2) Текущая цена больше минимальной? Да, то пункт (4)
3) Доставляем доску после указателя, если забор не кончился, добавляем цену с учетом штрафов порожденных ей и перемещаем  указатель. В случае добавления прыгаем в пункт (2)
4) Меняем доску под указаетлем если можем, сначала отнимаем штрафы порожденные предыдущей и ставим новую заместо нее и штрафы опять прибавляем. В случае смены прыгаем в пункт (2)
5) Убираем доску под указаетлем, снимаем штрафы, перемещаем указатель к началу на одну позицию. Если убрали первую доску в заборе, то конец, иначе прыгаем в пункт (4)

Задача похожа на задачу с коробкой, в которую надо положить предметы разного объема и веса, при этом добиться максимального веса при условии, что все предметы не помещаются в объем коробки.

Более элегантного решения не знаю.

Что-то в голову пришло, написал такую программу. Интересно, она работает?

uses crt;
var n,m:byte;
    sl:array[1..100]of string[6];
    sl2:array[1..100]of string;
    sh,sh2:array[1..100]of word;
    res,res2:string;
    i:word;
    c:char;
    k:set of char;
    nk:word;
    minn,min,sht:word;
function nod(a,b:longint):longint;
 var p1,p2,p3:longint;
 begin
 if a>b then
  begin p1:=a;p2:=b end
   else
  begin p1:=b;p2:=a end;
 while p2<>0 do
  begin
  p3:=p1 mod p2;
  p1:=p2;p2:=p3;
  end;
 nod:=p1;
 end;
function nok(a,b:longint):longint;
 begin
 nok:=a*b div nod(a,b);
 end;
function get(const s:string):word;
 var a,z,r:word;
 begin
 r:=0;
 for a:=1 to m do
  for z:=1 to length(s)-length(sl[a])+1 do
   begin
   if copy(s,z,length(sl[a]))=sl[a] then
    inc(r,sh[a]);
   end;
 get:=r;
 end;
procedure buildres(num:byte);
 var m:byte;
 begin
 res:='';
 m:=1;
 while length(res)<n do
  begin
  res:=res+sl2[num][m];
  m:=1+(m mod length(sl2[num]));
  end;
 end;
begin
clrscr;
fillchar(sl,sizeof(sl),0);
writeln('‚ўҐ¤ЁвҐ ¤«Ё­­г § Ў®а ');
readln(n);
writeln('‚ўҐ¤ЁвҐ зЁб«® б«®ў');
readln(m);
writeln('‚ўҐ¤ЁвҐ б«®ў  Ё ива дл');
k:=[];
for i:=1 to m do
 begin
 read(c);
 while c<>' ' do
  begin
  sl[i]:=sl[i]+upcase(c);
  read(c);
  end;
 readln(sh[i]);
 if length(sl[i])=1 then include(k,sl[i][1]);
 end;
if not('I' in k) then begin inc(m);sl[m]:='I';sh[m]:=0;end;
if not('N' in k) then begin inc(m);sl[m]:='N';sh[m]:=0;end;
if not('W' in k) then begin inc(m);sl[m]:='W';sh[m]:=0;end;
nk:=nok(length(sl[1]),length(sl[2]));
for i:=3 to m do
 nk:=nok(length(sl[i]),nk);
for i:=1 to m do
 begin
 sl2[i]:='';
 while length(sl2[i])<nk do
  sl2[i]:=sl2[i]+sl[i];
 sh2[i]:=get(sl2[i]);
 end;
minn:=1;buildres(1);min:=get(res);
for i:=2 to m do
 begin
 buildres(i);
 sht:=get(res);
 if sht<min then
  begin
  minn:=i;
  min:=sht;
  end;
 end;
buildres(minn);
res2:=res+res;
min:=get(copy(res2,1,n));sht:=1;
for i:=2 to length(res2)-n+1 do
 if get(copy(res2,i,n))<min then
  begin sht:=i;min:=get(copy(res2,i,n))end;
 
writeln('ЊЁ­Ё¬ «м­л© ива д: ',get(copy(res2,sht,n)));
writeln('ЏаЁ¬Ґа: ',copy(res2,sht,n));
readkey;
end.

2albom

работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D

Цитата wormball, 21.03.03, 18:30:18

2albom

работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D

тут даже и не кусок...

Да ну вас, грустно мне сегодня....

А пришло в голову то, что последовательность с наименьшим штрафом есть повторение некоторого слова, которое можно получить из исходных и некоторых других (если их нет в исходных). Потом мы расширяем все слова до нужной длинны (см вызов функции nok)и сравниваем их штрафы (их уже нужно считать самим). Ну и выбрав слово с наименьшим штрафом повторяем его n раз, и исчем в нем подстроку с минимальным штрафом. Она и есть ответ.