Решение задачи Орак и модели с Codeforces

Без пояснения   Просмотров: 57


В магазине есть n моделей, пронумерованных от 1 до n, размеры которых равны s1,s2,…,sn.

Орак купит некоторые из этих моделей и упорядочит их по возрастанию номеров (индексов, а не размеров).

Орак считает, что полученная расстановка красивая, если для любых двух соседних моделей с номерами ij и ij+1 (обратите внимание, что ij
Например, для 6 моделей с размерами {3,6,7,7,7,7}, он может купить модели с индексами 1, 2, и 6, и полученная расстановка будет красивой. Обратите внимание, что расстановка из одной модели также считается красивой.

Орак хочет знать, какое наибольше число моделей он может купить, и он может задавать вам эти вопросы по несколько раз.

Код

#include <bits/stdc++.h>

using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        b[i] = 1;
    }
    int mx = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 2; i * j <= n; ++j){
            if(a[i] < a[i * j])
                b[i * j] = max(b[i * j], b[i] + 1);
        }
        mx = max(mx, b[i]);
    }
    cout << mx << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться