2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбиение строки на палиндромы
Сообщение26.12.2010, 18:54 
Задача: разбить строку на минимальное число палиндромов
ссылка на задачу
Вот я написал программу, но на 59 тесте она выдаёт неверный ответ.
Будьте добры, подскажите, где здесь ошибка.
Идея алгоритма:
в matrix[i][j] хранится 1, если строка от i до j элемента - палиндром, иначе - 0
дальше применятеся динамическое программирование: W[i] - наилучшее разбиение первых i элементов.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
 
#include <iostream>

const int MaxStr = 4002;
int getl(char * in)
{
        int i = 0;
    while (in[i++]);
        return i-1;
};


int main()
{
        char* in = new char[MaxStr];
        std::cin>>in;

        int N = getl(in);
        char ** matrix = new char* [N];
        for(int i =0; i<N; i++)
        {
                matrix[i] = new char[N];
                for(int j = 0; j<N; j++)
                        matrix[i][j] = 0;
        }

        for(int i =0; i<N; i++)
                matrix[i][i] = 1;


        for(int i =1; i<N; i++)
                if (in[i-1] == in[i])
                        matrix[i-1][i] = 1;
        for(int  i=N-1; i>=0; i--)
                for(int  j =i+2; j<N; j++)
                {
                        if ((matrix[i+1][j-1] == 1)&&(in[i] == in[j]))
                                matrix[i][j] = 1;
                }


                int *W = new int[N+1];
                int *path = new int[N+1];
                for(int i =0; i<=N; i++)
                {
                        W[i] = 9999999;
                        path[i] = 999999;
                }
                W[0] = 0;
                path[0] = -1;
                for(int i =0; i<N; i++)
                        for(int j = i+1; j<=N;j++)
                        {
                                if ((matrix[i][j-1] ==1)&&(W[j]>W[i] +1))
                                {
                                        W[j] = W[i] + 1;
                                        path[j] = i;
                                }
                        }

                        int count = 0;
                        char* ANS = new char[MaxStr];
                        char* ANS2 = new char[MaxStr];
                        int point = 0;
                        int tmp = path[N];
                        int index = N;         
                        while(index>0)
                        {
                                count++;
                                for(;index>tmp; index--,point++)
                                        ANS[point] = in[index-1];
                                if (index == 0) break;
                                ANS[point] =' ';
                                point++;
                                tmp = path[tmp];
                        }
                std::cout<<count<<"\n";
                ANS2[point] = 0;
                for(int i  =0; i<point; i++)
                        ANS2[i] = ANS[point - i - 1];
                std::cout<<ANS2;

        return 0;
}
 

 
 
 
 Re: Разбиение строки на палиндромы
Сообщение28.12.2010, 23:58 
Ох, пардон, нашел глупейшую ошибку :cry: Вопрос снят, тему можно закрывать.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group