1

Тема: N повітряних кульок

У вас є ряд з N повітряних кульок і масив цілих A[N], якщо ви лопаєте кульку і, то ви отримуєте добуток А[лівий сусід]*А[ i]*A[правий сусід]. Для полегшення роботи з граничними умовами припускаємо, що ліворуч і праворуч від кульок висять кульки-охоронці, які не можна лопати і які мають пов'язані значення 1 і 1.

Скільки грошей ви можете заробити найбільше?

2

Re: N повітряних кульок

Лопнути всі кульки, крім груп, в яких непарна кількість від’ємних значень. Ви явно забули про якусь умову.

Подякували: FakiNyan, leofun012

3

Re: N повітряних кульок

quez написав:

Лопнути всі кульки, крім груп, в яких непарна кількість від’ємних значень. Ви явно забули про якусь умову.

Якби я написав А[i-1]*А[ i]*A[i+1], але я написав А[лівий сусід]*А[ i]*A[правий сусід], а сусіди в результаті лопань змінюються.

4

Re: N повітряних кульок

Yola написав:
quez написав:

Лопнути всі кульки, крім груп, в яких непарна кількість від’ємних значень. Ви явно забули про якусь умову.

Якби я написав А[i-1]*А[ i]*A[i+1], але я написав А[лівий сусід]*А[ i]*A[правий сусід], а сусіди в результаті лопань змінюються.

ну так а яка різниця? лопнули одну штуку, колекція змінилась, тепер беремо і заново лопаєм

5 Востаннє редагувалося koala (23.01.2016 12:16:53)

Re: N повітряних кульок

Тут, крім повного перебору, здається, нічого і нема.
(1000,-1,-1,-1,1000,-1,-1,-1,1000) дає максимум в 999999998 - але я не бачу способу знайти цей максимум на довших масивах зі схожими патернами. Якось так (python):

def max_pop(arr):
  return max([arr[i-1]*arr[i]*arr[i+1]+max_pop(arr[:i-1]+arr[i+2:]) for i in range(1,len(arr)-1)]+[0])

6

Re: N повітряних кульок

FakiNyan написав:

ну так а яка різниця? лопнули одну штуку, колекція змінилась, тепер беремо і заново лопаєм

лопнувши кульку з індексом 3 ви можете отримати A[2]*A[3]*A[4], але якщо кульку два вже лопнули то лівим сусідом буде 1 і ви отримаєте A[1]*A[3]*A[4].

koala написав:

Тут, крім повного перебору, здається, нічого і нема.
(1000,-1,-1,-1,1000,-1,-1,-1,1000) дає максимум в 999999998 - але я не бачу способу знайти цей максимум на довших масивах зі схожими патернами. Якось так (python):

def max_pop(arr):
  return max([arr[i-1]*arr[i]*arr[i+1]+max_pop(arr[:i-1]+arr[i+2:]) for i in range(1,len(arr)-1)]+[0])

еррр... Важко у мене з python. Але варіанти є. адже підзадачі повторюються, тобто є оптимальна підструктура. Значить розв'язки підзадач можна записувати у таблицю і використовувати їх замість обчислювати знов, ну прямо як з числами Фібоначі :) можна рекурсивна експоненційно, а можна і ні:)

7

Re: N повітряних кульок

пане Yola, я то зрозумів.
Я мав на увазі, що після кожного лопання починаємо спочатку. Ну або не спочатку, а з елементу i-1.
тобто, от лопаємо A3, зліва виходе A1, тепер лопаємо A1, хоча, виходе те саме, наче.

8

Re: N повітряних кульок

Ай, не так зрозумів умову - лопаємо ж одну кульку.

9 Востаннє редагувалося Yola (24.01.2016 12:27:41)

Re: N повітряних кульок

Якось так:

int MaxCoins(vector<int> nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int k = 2; k < n; ++k) {
        for (int left = 0; left < n - k; ++left) {
            int right = left + k;
            for (int i = left + 1; i < right; ++i)
                dp[left][right] = 
                    max(
                        dp[left][right], 
                        dp[left][i] + nums[left] * nums[i] * nums[right] + dp[i][right]
                        );
        }
    }

    return dp[0][n - 1];
}