Решение задачи "Палиндромы" с Меньшиков

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


Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.

Ограничения: 1 <= N <= 60.

Код

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
 
using namespace std;
 
string str;
vector<vector<long long> > F;
int n;
void input()
{
    cin>>str;
    n = str.size();
    F = vector<vector<long long> >(n,vector<long long>(n,0));
}
void solve()
{
    int j;
    for (int k = 0; k < n; k++)
    {
        for (int i=0; i<n; i++)
        {
            j = i+k;
            if (j==n)
                break;
            if (i == j)
                F[i][j] = 1;
            else
            {
                if (str[i] != str[j])
                    F[i][j] = F[i+1][j] + F[i][j-1] - F[i+1][j-1];
                else
                    F[i][j] = F[i+1][j] + F[i][j-1] + 1;
            }
        }
    }
    cout<<F[0].back();
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    input();
    solve();
    return 0;
}
 

         

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


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

Комментарии

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