将元素数组分解为最少数量的回文

Question

你会如何解决一个问题：

A given sequence of integers can be broken up into parts such that each of them is a palindrome. Consider the sequence 34,45,34,56,34. This can be broken up into 3 palindrome sequences with 34, 45, 34 constituting the first, 56 constituting the second and 34 constituting the third. It can also be broken in 5 palindrome sequences each containing a single number. Thus, there may be many different ways to break up a given sequence into palindrome sequences. We want to determine the smallest number C such that the given sequence can be broken up into C palindrome sequences.

我的解决方案是这样的：找到数组的最大回文（最大长度的回文），取除了这个最大回文之外的数组其余部分，并尝试找到它的最大回文等等，同时递增计数的回文数。

这是我目前拥有的：

#include <algorithm>
#include <iostream>
#include <vector>
#define print(arr) for(auto pos = arr.begin(); pos != arr.end(); ++pos) cout << *pos << " "; cout << endl;
typedef long long int ll;
using namespace std;

int calc(vector<ll> A, int N) {
    int i = N;
    vector <ll> t1, t2;
    while (i >= 0) {
        t1 = vector <ll> (A.begin(), A.begin()+i);
        t2 = vector <ll> (t1.rbegin(), t1.rend());
        if (t1 == t2) return i;
        i--;
    }
    return 0;

}
int main() {
    int N;
    ll x;
    cin >> N;
    vector <ll> A(N);

    for (int i = 0; i < N; i++) {
        cin >> x;
        A[i] = x;

    }
    int temp = calc(A,N);
    int c = 0;

    while (temp != 0) {
        A = vector <ll> (A.begin()+temp, A.end());
        N = (int)A.size();
        temp = calc(A, N);
        c++;
    }
    cout << c << endl;
}

但是，我弄错了 3 个测试用例。后来意识到我的程序为测试用例输出 4 而不是 2：N=8, {2, 1, 2, 1, 2, 3, 2, 1} 它需要回文为 {2,1,2,1,2 }, {3}, {2}, {1} 而它应该是 {2,1,2}, {1,2,3,2,1}。如果我反转向量并计算两者之间的最小答案，我将得到此测试用例的正确答案 2，但对于 Codechef 上的其他人，我仍然得到 2 个测试用例错误，可能出于与我错误相同的原因。

无论如何，知道我该如何改进吗？

Link codechef 上的问题：https://www.codechef.com/ZCOPRAC/problems/ZCO15001 来自正在进行的比赛，但比赛只是在印度举行的 Zonal Computing Olympiad 的练习赛。

Answer 1

这是典型的动态规划问题。您可以使用 O(N ^ 2) 复杂度轻松解决它，其中 N 是输入字符串的大小。

首先，你可以预先计算出所有O(N ^ 2)复杂度的回文来回答子串[i, j]是否是回文在O(1)中（让它成为你的练习） .

然后你可以计算数组dp，其中dp[i]是子字符串[0, i]的答案。要找到 dp[i] 你需要做： dp[i] = min(dp[i], dp[j] + 1) for all j where j < i and substring [j + 1, i] is palindrome.这里使用回文预计算来检查 O(1) 中的子字符串 [j + 1, i] 是否为回文。 dp[0]当然是1。

答案是dp[N - 1]。

P.S。所有索引都从 0 开始。

将元素数组分解为最少数量的回文

Breaking an array of elements into least number of palindromes

c++

algorithm

palindrome