时间戳

首页 > 解决方案 > 寻找长度为 3 的递增序列的最低成本的算法

algorithm - 寻找长度为 3 的递增序列的最低成本的算法

问题描述

假设我们有一个长度为 n 的序列。这个序列中的每个数字都有一个权重。我们想通过动态规划找到长度为 3 的最小加权递增子序列。我们怎么能这样做？

例子：

顺序：2 4 5 4 10

重量：40 30 20 10 40

答案是 90 ( 2 4 10)

标签： algorithmdynamic-programming

解决方案

我已经在一些 codeforces 回合中解决了这个完全相同的问题。（http://codeforces.com/contest/987/problem/C）

我的解决方案是 O(N^2)，其中 N 是房屋数量。

它的工作原理如下，对于每个房子 k，我将搜索属于 K 右边的最便宜的房子。

一旦我获得了这些信息，我就尝试所有可能的对 (i, j)，使得 height[i] < height[j] 并将比位置 j 的房子高的最便宜的House 相加。

这是我的代码！

#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），但代码更脏，并且上面有一些葡萄牙语变量名。

推荐阅读