题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>


using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010;
int a[N], b[N];
PII c[N];

int main()
{
    int T;
    cin >> T;
    while(T -- )
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++)
        {
            cin >> a[i];
            c[i] = {a[i], i};
        }

        sort(c, c + n);

        LL res = 0;
        for (int j = 0; j < n; j ++)
        {
            int v = c[j].first, i = c[j].second;
            int l = (i + n - 1) % n, r = (i + 1) % n;
            b[i] = 1;
            if (v > a[l]) b[i] = max(b[i], b[l] + 1);
            if (v > a[r]) b[i] = max(b[i], b[r] + 1);
            res += b[i];
        }
        cout << res << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla