Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → N повітряних кульок
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
У вас є ряд з N повітряних кульок і масив цілих A[N], якщо ви лопаєте кульку і, то ви отримуєте добуток А[лівий сусід]*А[ i]*A[правий сусід]. Для полегшення роботи з граничними умовами припускаємо, що ліворуч і праворуч від кульок висять кульки-охоронці, які не можна лопати і які мають пов'язані значення 1 і 1.
Скільки грошей ви можете заробити найбільше?
Лопнути всі кульки, крім груп, в яких непарна кількість від’ємних значень. Ви явно забули про якусь умову.
Якби я написав А[i-1]*А[ i]*A[i+1], але я написав А[лівий сусід]*А[ i]*A[правий сусід], а сусіди в результаті лопань змінюються.
quez написав:Лопнути всі кульки, крім груп, в яких непарна кількість від’ємних значень. Ви явно забули про якусь умову.
Якби я написав А[i-1]*А[ i]*A[i+1], але я написав А[лівий сусід]*А[ i]*A[правий сусід], а сусіди в результаті лопань змінюються.
ну так а яка різниця? лопнули одну штуку, колекція змінилась, тепер беремо і заново лопаєм
Тут, крім повного перебору, здається, нічого і нема.
(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])ну так а яка різниця? лопнули одну штуку, колекція змінилась, тепер беремо і заново лопаєм
лопнувши кульку з індексом 3 ви можете отримати A[2]*A[3]*A[4], але якщо кульку два вже лопнули то лівим сусідом буде 1 і ви отримаєте A[1]*A[3]*A[4].
Тут, крім повного перебору, здається, нічого і нема.
(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. Але варіанти є. адже підзадачі повторюються, тобто є оптимальна підструктура. Значить розв'язки підзадач можна записувати у таблицю і використовувати їх замість обчислювати знов, ну прямо як з числами Фібоначі 
можна рекурсивна експоненційно, а можна і ні:)
пане Yola, я то зрозумів.
Я мав на увазі, що після кожного лопання починаємо спочатку. Ну або не спочатку, а з елементу i-1.
тобто, от лопаємо A3, зліва виходе A1, тепер лопаємо A1, хоча, виходе те саме, наче.
Ай, не так зрозумів умову - лопаємо ж одну кульку.
Якось так:
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];
}Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися