发现回文序列的数量从一组给定的数字 [英] Finding the number of palindromic sequences from a given set of numbers

问题描述

假设我们给出了一组数字像20 40 20 60 80 60 它可以分为2回文序列： 20 40 20 和 60 80 60 。 它也可以被分解成各含有一个单一的数字6回文序列

Suppose we are given a set of numbers like 20 40 20 60 80 60 It can be broken up into 2 palindromic sequences: 20 40 20, and 60 80 60. It can also be broken into 6 palindromic sequences each containing a single number.

如何找到在C中最小的数字回文序列可以从一组给定的数字++的？

How do we find the smallest number of palindromic sequences possible from a given set of numbers in c++?

PS-这不是我的家庭作业。真正的问题。

PS- This is not my homework. Genuine question.

推荐答案

一个简单的方法首先查看每个的O（N ³ ）子序列和检查，看它是否是一个回文。一旦我们知道哪些子序列是回文，我们能做到动态规划为O（n ² ）的时间来寻找连续的子序列，涵盖了整个序列的最小数量。

A straightforward approach begins by looking at each of the O(n³) subsequences and checking to see if it's a palindrome. Once we know which subsequences are palindromic, we can do dynamic programming in O(n²) time to find the minimal number of consecutive subsequences that cover the whole sequence.

对于输入 20 40 20 60 80 60 ，C ++实现以下版画 [20 40 20] [60 80 60] 。

For the input 20 40 20 60 80 60, the C++ implementation below prints [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;
}

这篇关于发现回文序列的数量从一组给定的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！