$\texttt{AcWing 4214. 三元组}$

题目描述

给定两个长度为 $n$ 的整数序列 $s_1,s_2,…,s_n$ 和 $c_1,c_2,…,c_n$。

请你找到一个三元组 $(i,j,k)$，满足以下所有条件：

• $i<j<k$
• $s_i<s_j<s_k$
• $c_i+c_j+c_k$ 尽可能小

输出 $c_i+c_j+c_k$ 的最小可能值。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $s_1,s_2,…,s_n$。

第三行包含 $n$ 个整数 $c_1,c_2,…,c_n$。

输出格式

如果满足条件的三元组不存在，则输出 $−1$。

否则，输出 $c_i+c_j+c_k$ 的最小可能值。

数据范围

前 $5$ 个测试点满足 $3≤n≤10$。
所有测试点满足 $3≤n≤3000, 1≤s_i≤10^9, 1≤ci≤10^8$。

输入样例1：

5
2 4 5 4 10
40 30 20 10 40

输出样例1：

90

输入样例2：

3
100 101 100
2 4 5

输出样例2：

-1

输入样例3：

10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13

输出样例3：

33

枚举

先枚举每个 $j$, 把 $j$ 固定好后, 再往前枚举 $i$ 并把符合条件的 $c_i$ 记录下来, 再往后枚举 $k$, 更新答案的方法同理。枚举完 $i$ 和 $k$ 后, 以 $j$ 为中心时的答案就是 $左边 c_i 的最小值 + c_j + 右边 c_k 的最小值$。最后取个min即可。

时间复杂度 $O(n^2)$

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010, inf = 5e8;
int s[N], c[N];
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    for (int i = 1; i <= n; i ++ ) cin >> c[i];
    int res = inf;
    for (int j = 1; j <= n; j ++ ){
        int left = inf;
        for (int i = 1; i < j; i ++ )
            if(s[i] < s[j])
                left = min(left, c[i]);
        int right = inf;
        for (int k = j + 1; k <= n; k ++ )
            if(s[k] > s[j])
                right = min(right, c[k]);
        res = min(res, left + c[j] + right);
    }
    cout << (res == inf ? -1 : res);
}