алгоритм нахождения наименьшей стоимости возрастающей последовательности длины 3

Question

предположим, что у нас есть последовательность длины n.каждое число в этой последовательности имеет вес.мы хотим найти наименее взвешенную возрастающую подпоследовательность длины 3 с динамическим программированием.как мы можем это сделать?

пример:

последовательность: 2 4 5 4 10

вес: 40 30 20 10 40

ответ 90(2 4 10)

Answer 1

Я решил эту проблему точно так же в каком-то раунде Codeforces.(http://codeforces.com/contest/987/problem/C)

Мое решение - O (N ^ 2), где N - количество домов.

Это работает следующим образом, для каждого дома k я буду искать самый дешевый домкоторый принадлежит справа от K.

Как только я получу эту информацию, я просто попробую все возможные пары (i, j), чтобы высота [i] <высота [j], и суммировал для этой пары самый дешевый дом, которыйвыше дома в позиции j. </p>

Вот мой код!

#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 0x3f3f3f3f;

int main()
{
    int n;
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vector<int> height(n);
    for(int i = 0; i < n; ++i) cin >> height[i];

    vector<int> cost(n);
    for(int i = 0; i < n; ++i) cin >> cost[i];

    vector<int> cheapestToTheRight(n, inf);

    cheapestToTheRight[n-1] = inf;

    for(int k = n - 2; k >= 0; --k)
    {
        for(int nxt = k + 1; nxt < n; ++nxt)
        {
            if(height[nxt] > height[k])
            {
                cheapestToTheRight[k] = min(cheapestToTheRight[k], cost[nxt]);
            }
        }
    }

    int ans = inf;

    for(int i = 0; i < n; ++i)
    {
        for(int j = i + 1; j < n; ++j)
        {
            if(height[i] < height[j])
            {
                if(cheapestToTheRight[j] != inf)
                {
                    ans = min( ans, cost[i] + cost[j] + cheapestToTheRight[j]);
                }
            }
        }
    }

    if(ans == inf)
    {
        cout << -1 << endl;
    }

    else cout << ans << endl;
    return 0;
}

Вот ссылка на мое подчинение (http://codeforces.com/contest/987/submission/38734180),, но код более грязный и снекоторые имена португальских переменных на нем.