#!/usr/bin/env python3 # Nacitanie vstupu: na vstupe budu zadane cisla oddelene medzerou. Funkcia # input vrati string, funkcia split ho naseka implicitne podla medzier a # funkcia map na kazdu cast aplikuje funkciu int, ktora vyrobi cele cisla. Fcia # list vrati objekt typu list. nums = [0] + list(map(int, input().split())) # Na zaciatok umiestnim pomocnu nulu. n = len(nums) # V dp[i] je najlepsi mozny vysledok taky, ze posledne '+' sa nachadza medzi # nums[i] a nums[i+1]. V dp[n] bude ulozeny celkovy vysledok. dp = [0] * n # V pp[i] si pamatame, ze kde sa nachadzalo posledne '+' po uzavreti dp[i], aby # sme na konci vedeli vsetky operatory doplnit. lp = [0] * n # Vypocet: # Zlava postupne berieme cisla. for i in range(1, n): # Pozrieme sa na kazde dp[j], pre j < i, ... for j in range (0, i): # ... spocitame prod = dp[j+1] * ... * dp[i] prod = 1 for k in range(j+1, i+1): prod *= nums[k] # ... a skusime, ze ci dp[j] + prod dava lepsi vysledok ako aktualny # najlepsi ulozeny v dp[i]. if dp[j] + prod > dp[i]: dp[i] = dp[j] + prod lp[i] = j # Zapamatame si kde bolo posledne '+'. # Vypis (cisla budu v opacnom poradi): print(dp[n-1], end=' ') # Vypiseme vysledok. print('=', end=' ') i = n-1 while i > 0: print(nums[i], end=' ') j = i-1 # Do najblizsieho '+' doplname nasobenie. while j > lp[i]: print('*', end=' ') print(nums[j], end=' ') j -= 1 # Vypiseme '+' ale ignorujeme pomocnu nulu na zaciatku. i = lp[i] if i != 0: print('+', end=' ') print()