Решение задачи "Головоломка умножения" с Меньшиков

Без пояснения   Просмотров: 9

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.

Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки

10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.

Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:

1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.

Код 

#include <iostream>
#include <vector>
#include <cstdio>
 
using namespace std;
 
int n;
vector<int> mas;
vector<vector<int> > mem;
void input()
{
    cin>>n;
    mas.resize(n);
    for (int i=0;i<n;i++)
        cin>>mas[i];
    mem = vector<vector<int> > (n,vector<int>(n));
}
 
void solve()
{
    for (int len = 2; len < n; len++)
    {
        for (int i=0;i<n;i++)
        {
            int j = i + len;
            if (j == n)
                break;
            int res = 1e9;
            for (int m = i+1; m<=j-1; m++)
            {
                int cur = mem[i][m] + mas[i] * mas[m] * mas[j] + mem[m][j];
                res = min(res,cur);
            }
            mem[i][j] = res;
        }
    }
    cout<<mem[0][n-1];
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться