1

Тема: Оптимізація програми

Доброго дня! Дуже потрібна допомога з однією задачею з теми "Динамічне програмування" на сайті e-olymp.com

Мишка і зернинки

В індійському храмі підлогу прямокутної форми вимощено однаковими квадратними плитками 1 x 1, на кожну з яких насипано від 0 до k зернинок (k ≤ 30000). Розміри підлоги m х n. Мишка вибігає з лівого нижнього кута підлоги храму i рухається до входу у іншу нірку, розміщену у протилежному кутку. Мишка може рухатись лише праворуч або вперед, збираючи всі зернинки з плитки, на якій вона знаходиться. Знайти маршрут, рухаючись по якому мишка збере найбільшу кількість зернин.

Вхідні дані
Перший рядок містить числа m та n - розміри підлоги (1 ≤ m, n ≤ 100). Далі йде m рядків, починаючи з верхнього, у кожному з яких розміщено n чисел – кількість зернинок на відповідній плитці.

Вихідні дані
Вивести маршрут руху мишки у форматі: RRFFFRF (F - крок вперед, R - крок праворуч).

Мій розв'язок наступний:

a,b=[int(i) for i in input().split()]
c=[]
for i in range(a):
    c=c+[[int(i) for i in input().split()]]
x=0
y=a-1
res=""
for i in range(1, b):
    c[y][i]=c[y][i]+c[y][i-1]

for i in range(y-1,-1,-1):
    c[i][x]=c[i][x]+c[i+1][x]

for i in range(y-1,-1,-1):
    for j in range(1,b):
        c[i][j]=c[i][j]+max(c[i+1][j],c[i][j-1])

for i in range(a):
    c[i]=c[i][::-1]

c=c[::-1]

while True:
    if y==0 and x==b-1:
        break
    elif y==0:
        x=x+1
        res=res+'R'
    elif x==b-1:
        y=y-1
        res=res+'F'
    elif c[y][x+1]>c[y-1][x]:
        x=x+1
        res=res+'R'
    elif c[y][x+1]<c[y-1][x]:
        y=y-1
        res=res+'F'
print(res[::-1])

На скільки я зрозумів, сам розв'язок правильний, але великі матриці обробляє занадто довго. Як мені оптимізувати дану програму, можливо є простіший алгоритм? Але, я поки що вмію тільки так))) Допоможіть будь-ласка!

2

Re: Оптимізація програми

Будь ласка, назвіть змінні нормально. І напишіть десь в коментарі, як у вас нумеруються комірки (якщо я зрозумів, то перша координата - вертикальна, друга - горизонтальна мишка починає в комірці з координатами (y-1,0), а приходить в (0,x-1), що не дуже зручно).
І я не певен, що це коректний алгоритм, але розбирати такий код - собі дорожче.

3 Востаннє редагувалося ykozolup (08.02.2018 16:52:26)

Re: Оптимізація програми

# запит довжини ти ширини матриці
m,n=[int(i) for i in input().split()]
# створення матриці
c=[]
# запит рядків матриці
for i in range(m):
    c=c+[[int(i) for i in input().split()]]

# початкове положення миші по горизонталі
x=0
# початкове положення миші по вертикалі 
y=m-1
# початкове значення відповіді
res=""
# обробка кожного елемента найнижчого рядка, заміна значень на суму попередньго
# та даного елемента
for i in range(1, n):
    c[y][i]=c[y][i]+c[y][i-1]
# обробка кожного елемента першого стовпчика, заміна значень на суму попереднього
# та даного елемента
for i in range(y-1,-1,-1):
    c[i][x]=c[i][x]+c[i+1][x]

# обробка інших елементівпо рядах, що залишилися, заміна їх на суму цього елмента
# там максимального серед двох сусідніх (внизу та зліва)
for i in range(y-1,-1,-1):
    for j in range(1,n):
        c[i][j]=c[i][j]+max(c[i+1][j],c[i][j-1])
# зеркальний запис кожного ряда матриці по вертикалі
for i in range(m):
    c[i]=c[i][::-1]

# зеркальтний запис матриці по горизонталі
c=c[::-1]

# обробка всіх елементів матриці з нижнього лівого кута, рух у напрямку
# найбільших елементів, зміна значення відповіді в залежності від напрямку руху
while True:
    if y==0 and x==n-1:
        break
    elif y==0:
        x=x+1
        res=res+'R'
    elif x==n-1:
        y=y-1
        res=res+'F'
    elif c[y][x+1]>c[y-1][x]:
        x=x+1
        res=res+'R'
    elif c[y][x+1]<c[y-1][x]:
        y=y-1
        res=res+'F'

# виведення зеркального відображення відповіді
print(res[::-1])

Ну як зміг, вибачте, я ще тільки початківець) Буду дуже вдячний, якщо ви зрозумієте))))

4 Востаннє редагувалося koala (08.02.2018 17:30:57)

Re: Оптимізація програми

Ви зробили не те, що я просив (крім заміни a,b на m,n), ну то біс із ним.
Тут немає кричущих неоптимальностей (все одно доведеться кожну з m*n комірок обійти, а нічого складнішого ви не робите), тут є зациклення. Що станеться, якщо два шляхи матимуть однакову вагу? Ваш вічний цикл нічого не змінить (бо жодна гілка не спрацює) і повторить ітерацію. Просто виправіть останній elif на else (а ще краще - запишіть складну умову, коли відбувається рух вперед, і якщо вона виконується - додавайте 'F', а якщо ні - 'R', чи vice versa).
І не треба спершу обертати матрицю, а потім відповідь, треба просто рухатися в зворотному напрямку.
І взагалі не треба робити його вічним, а поки довжина рядка не стане m+n.

Подякували: ykozolup1

5

Re: Оптимізація програми

Дякую!!! Все зрозуміло! Ви - крутий)

6

Re: Оптимізація програми

Ще раз дякую, програма пройшла всі тести. Я просто замінив elif на else. Хоча все одно трішки підправлю, щоб було ще краще)

7

Re: Оптимізація програми

Є загальна порада - завжди робити else. Навіть якщо він абсурний.

умова = bool(func())
if умова==true:
  ...
elif умова==false:
 ...
else:
  print("Повідомте розробникам, їм дуже цікаво, як ви примудрилися сюди потрапити")
  write_dump()
  exit()

Написати таке - 1 хвилина. Зневаджувати без цього потім можна кілька діб.

Прихований текст

P.S. Конкретно цей приклад, звісно, недолугий, тут слід зробити

if умова:
  ...
else:
 ...

Але else має бути обов'язково.