Блог пользователя Berzhik

Помогите с задачей
Автор Berzhik, 13 лет назад, По-русски

На acmp.ru недавно выкинули 100 новых задач, и вот я нарвался на такую задачу http://acmp.ru/index.asp?main=task&id_task=553 На первый взгляд она была простая динамическое программирование на таблицах, но когда я её написал то у меня не прошёл 5 тест, хотя все мои тесты он проходит правильно.
Вот моя основная программа
 read(n);
 for i:=1 to n do
   read(b[i],c[i]);
 for i:=n-1 downto 1 do
  for j:=i+1 to n do
   a[i,j]:=min(a[i+1,j],a[i,j-1])+b[i]*c[j];
 write(a[1,n]);
Помогите найти ошибку

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот предположим что у нас четыре блока.
Вы в своей динамике не рассматриваете такого варианта для сбора - сначала собрать 1 и 2, потом 3 и 4, потом объединить полученные два куска.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я об этом думал вот другой код
      read(n);
      for i:=1 to n do
       read(b[i],c[i]);
      for i:=1 to n-1 do
       for j:=1 to n-i+1 do
       a[j,i+j]:=min(a[j,i+j-1],a[j+1,i+j])+b[j]*c[j+i];
      write(a[1,n]);
    Который берёт этот тест, но и он не проходит 5 тест
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      Нет не берёт.

      1. for j:=1 to n-i+1 do, правый предел кажется не такой.

      2. Рассмотрите как получается ответ a[1,4]. У вас он получается из a[1,3] или из a[2,4], а должен ещё рассматриваться случай a[1,2]+a[3,4].

      Нужно понять что к состоянию a[i,j] можно прийти не двумя способами как у вас, а j-i способами.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, буду думать полное решение
→ Ответить