Решение задачи Еще одна задача про палиндромы с Codeforces

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


Вам задан массив a, состоящий из n целых чисел.

Ваша задача — определить, содержит ли a какую-то подпоследовательность длины хотя бы 3, которая является палиндромом.

Напомним, что массив b называется подпоследовательностью массива a, если b может быть получен удалением некоторого (возможно, нулевого) количества элементов из a (не обязательно подряд идущих) без изменения порядка оставшихся элементов. Например, [2], [1,2,1,3] и [2,3] являются подпоследовательностями [1,2,1,3], а [1,1,2] и [4] — нет.

Также напомним, что палиндром — это массив, который читается одинаково как слева направо, так и справа налево. Другими словами, массив a длины n является палиндромом, если ai=an−i−1 для всех i от 1 до n. Например, массивы [1234], [1,2,1], [1,3,2,2,3,1] и [10,100,10] являются палиндромами, а массивы [1,2] и [1,2,3,1] — нет.

Вам необходимо ответить на t независимых наборов тестовых данных.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t, n;
    cin >> t;
    for(int i = 0; i < t; ++i){
        cin >> n;
        vector<int> str(n);
        for(int i = 0; i < n; ++i){
            cin >> str[i];
        }
        vector<vector<int> > a;
        vector<int> temp;
        for(int i = 0; i < str.size(); ++i){
            temp.clear();
            vector<int> temp(str.size());
            a.push_back(temp);
        }
        for(int i = 0; i < str.size(); ++i){
            a[i][i] = 1;
        }

        for(int i = 0; i < str.size() - 1; ++i){
            int t = 0;
            for(int j = 1 + i; j < str.size(); ++j){
                if(str[t] != str[j]){
                    a[t][j] = max(a[t + 1][j], a[t][j - 1]);
                }
                else{
                    a[t][j] = a[t + 1][j - 1] + 2;
                }
                ++t;
            }
        }
        if(a[0][str.size() - 1] > 2)
            cout << "YES";
        else
            cout << "NO";
        cout << endl;
    }
    return 0;
}

         

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



Комментарии

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