P1637 三元上升子序列 题解

WydnksqhbD · 2024-03-15 17:57:52 · 算法·理论

P1637 三元上升子序列 题解

思路

暴力出奇迹。

记 l_i,r_i 分别为 a_i 左边 <a_i 的元素个数和 a_i 右边 >a_i 的元素个数。则 thair 的个数为 \sum_{i=1}^{n}l_i\times r_i。

暴力枚举即可。复杂度 O(n^2)，可过。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
long long ans;
int a[N];
int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++)
    {
        int sum1 = 0, sum2 = 0;
        for (int j = i - 1; j > 0; j --)
        {
            if (a[j] < a[i])
            {
                sum1 ++;
            }
        }
        for (int j = i + 1; j <= n; j ++)
        {
            if (a[j] > a[i])
            {
                sum2 ++;
            }
        }
        ans += sum1 * sum2;
    }
    cout << ans << endl;
    return 0;
}