寻找长度为 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) 使得 height[i] < height[j] 并将比位置 j 处的房子高的最便宜的房子加到这一对上。

这是我的代码!

#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 )，但代码比较脏，上面有一些葡萄牙语变量名。