Нахождение количества палиндромных последовательностей из заданного набора чисел

Question

Пусть дано множество чисел, как 20 40 20 60 80 60 Он может быть разбит на 2 палиндромных последовательности: 20 40 20 и 60 80 60. Он также может быть разбит на 6 палиндромных последовательностей, каждый из которых содержит одно число.

Как найти наименьшее количество палиндромных последовательностей из заданного набора чисел в C++?

PS- Это не моя домашняя работа. Подлинный вопрос.

Answer 1

Прямой подход начинается с рассмотрения подпоследовательностей и проверки, чтобы убедиться, что это палиндром. Как только мы узнаем, какие подпоследовательности являются палиндромными, мы можем сделать динамическое программирование в O (n) времени, чтобы найти минимальное количество последовательных подпоследовательностей, которые охватывают всю последовательность.

Для ввода 20 40 20 60 80 60, реализация на C++ под фотографиями [20 40 20] [60 80 60].

#include <cstdio> 
#include <vector> 
using namespace std; 

int main() { 
    // Read the data from standard input. 
    vector<int> data; 
    int x; 
    while (scanf("%d", &x) != EOF) { 
    data.push_back(x); 
    } 
    int n = data.size(); 

    // Look at every subsequence and determine if it's a palindrome. 
    vector<vector<bool> > is_palindrome(n); 
    for (int i = 0; i < n; ++i) { 
    is_palindrome[i] = vector<bool>(n); 
    for (int j = i; j < n; ++j) { 
     bool okay = true; 
     for (int left = i, right = j; left < right; ++left, --right) { 
     if (data[left] != data[right]) { 
      okay = false; 
      break; 
     } 
     } 
     is_palindrome[i][j] = okay; 
    } 
    } 

    // Dynamic programming to find the minimal number of subsequences. 
    vector<pair<int,int> > best(n); 
    for (int i = 0; i < n; ++i) { 
    // Check for the easy case consisting of one subsequence. 
    if (is_palindrome[0][i]) { 
     best[i] = make_pair(1, -1); 
     continue; 
    } 
    // Otherwise, make an initial guess from the last computed value. 
    best[i] = make_pair(best[i-1].first + 1, i-1); 
    // Look at earlier values to see if we can improve our guess. 
    for (int j = i-2; j >= 0; --j) { 
     if (is_palindrome[j+1][i]) { 
     if (best[j].first + 1 < best[i].first) { 
      best[i].first = best[j].first + 1; 
      best[i].second = j; 
     } 
     } 
    } 
    } 

    printf("Minimal partition: %d sequences\n", best[n-1].first); 
    vector<int> indices; 
    int pos = n-1; 
    while (pos >= 0) { 
    indices.push_back(pos); 
    pos = best[pos].second; 
    } 
    pos = 0; 
    while (!indices.empty()) { 
    printf("[%d", data[pos]); 
    for (int i = pos+1; i <= indices.back(); ++i) { 
     printf(" %d", data[i]); 
    } 
    printf("] "); 
    pos = indices.back()+1; 
    indices.pop_back(); 
    } 
    printf("\n"); 

    return 0; 
}