No comments

i think answer is
3 polindroms: AB ZZBBBZZ A

Смотрю с любовью на свои более 10-летней давности попытки решать задачи. Спасибо, ACM.Timus!

Accepted!!!!
BFS - very good thing!!!!

#include <iostream>
#include <algorithm>
#include <string>

unsigned counter = 0;
void printPalindroms(unsigned short *splitIndex, unsigned short i, const std::string& str){
    if(splitIndex[i] == 0){
        std::cout<<str.substr(0, i+1)<<" ";
    }else{
        printPalindroms(splitIndex, splitIndex[i]-1, str);
        std::cout<<str.substr(splitIndex[i], i + 1 - splitIndex[i])<<" ";
    }
}

int main()
{
    std::string strr;
    std::cin>>strr;
    const char* str = strr.data();

    unsigned length = strr.size();
    unsigned arrSize = (length*length + length)/2;
    bool *pArrData = new bool[arrSize];
    bool **pArr = new bool*[length];

    unsigned short *splitWeights = new unsigned short [length];
    unsigned short *splitIndex = new unsigned short[length];

    std::fill(pArrData, pArrData + arrSize, false);
    std::fill(splitWeights, splitWeights + length, length +2);
    std::fill(splitIndex, splitIndex + length, 0);

    unsigned offset = 0;
    for(unsigned i = 0; i<length; ++i){
        pArr[i] = pArrData + offset;
        offset += length - i;
    }

    // init the first row
    std::fill(pArr[0], pArr[0] + length, true);

    //init the second row
    for(unsigned i = 0; i<length - 1; ++i){
        if(str[i] == str[i+1]){
             pArr[1][i] = true;
        }
    }

    for(unsigned i = 2; i < length; ++i){
        for(unsigned j = 0; j< length - i; ++j){
            if(pArr[i-2][j+1] && str[j] == str[j+i]){
                pArr[i][j] = true;
            }
        }
    }

    for(unsigned  i = 0; i < length; ++i){
        if(pArr[i][0] == true){
            splitWeights[i] = 0;
            splitIndex[i] = 0;
        }else{
            for(unsigned j = 1; j <= i; ++j){
                if(pArr[i-j][j]){
                    unsigned short temp = splitWeights[j-1] + 1;
                    if(temp < splitWeights[i]){
                        splitWeights[i] = temp;
                        splitIndex[i] = j;
                    }
                }
            }
        }
    }

    std::cout<<splitWeights[length -1] + 1<<std::endl;

    printPalindroms(splitIndex, length - 1, strr);

    delete[] splitIndex;
    delete[] splitWeights;
    delete[] pArr;
    delete[] pArrData;


    return 0;
}

Ошибка где-то тут:




string line;
bool check(int s,int e)
{
    string temp;
    for(int i=s; i<=e; i++)
        temp.push_back(line[i]);
    string temp2=temp;
    reverse(temp.begin(),temp.end());
    if(temp==temp2)
        return true;
    return false;
}
int dp[4005][4005];
int palindrome(int s,int e)
{
    if(s>=e)
        return 0;
    if(dp[s][e]!=-1)
        return dp[s][e];
    int ans=(1<<30);
    for(int i=s; i<e; i++)
        if(check(s,i))
        {
            ans=min(ans,1+palindrome(i+1,e));

        }
    return dp[s][e]=ans;
}
vector<string>anss;
void print(int s,int e)
{
    int b=palindrome(s,e);
    if(b==1)
    {
        string temp;
        for(int i=s; i<e; i++)
            temp.push_back(line[i]);
            anss.push_back(temp);

        return;
    }
    for(int i=s; i<e; i++)
        if(b==1+palindrome(i+1,e))
        {
             string temp;
           for(int j=s;j<=i;j++)
             temp.push_back(line[j]);
            anss.push_back(temp);

           print(i+1,e);
           break;
        }

}
int main()
{
    cin>>line;
    int len;
    len=line.size();
    anss.clear();
    memset(dp,-1,sizeof dp);
    cout<<palindrome(0,len)<<endl;
    print(0,len);
    len=anss.size();
    for(int i=0;i<len-1;i++)
        cout<<anss[i]<<" ";
    cout<<anss[len-1]<<"\n";



}

Edited by author 22.08.2018 12:26

Edited by author 22.08.2018 12:26

It is something unique
I have had WA20, WA23, TLE32, MLE56
But never WA42

Nevermind, this test case helped me find my mistake: "ababbaa"

you are probably considering to get rid of palindromes as early as possible

for example, consider the case "aabba"

if you say it is 3 palindromes: "aa", "bb", and "a", then you are wrong, since it can be "a" and "abba"

One can think like that:
Let a(k) be the amount of palindromes in [0,k]. Then we have recursion:
a(k)=MIN{ 1 if [0,k] is pm  , MIN (from i = 0 to k -1) OF a(i) + 1   if [i,k] is pm}
        { 0 else                                          a(i) + k-i else          }

I consider ASK to be absolutely right concerning data structure He proposed.

Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)

whats the ans for 'abzzbbbzza'?

i didn't get it how it will become n^2  because for l=1 to l=n  is one loop and for r=l to r=n is inside loop and for    checking it is palindrome is another loop    so i don't get how it will be n^2 can you please explain me


i am very confused here please help me

OK...I have got it...in Ural...in C...You must write like boolflag == 1...You can not write like boolflag,which works in my computer...

aaaabaaa
correct answer is
2
a aaabaaa

I spotted a bug. Will fix it first and try again.

Give me your code !  I also WA 19,but I find write wrong dp[i]>dp[j-1]+1 to  dp[i]>dp[j]^……