Arghhh… this is the problem that i missed out at the contest last december… still feeling sad not to be able to solve it at that time… If you wanna take a look at the problem, you can go here. Well, today i redo it, and submitted it in UVa, and AC… actually my idea at the contest is correct…but i just hesitate to do it, felt not very sure about it, and ended up doing on that damn problem A!!    Really sad larrr….if only at that time, i focused on doing that problem, our team might solved 4 problems in the end… Well, it is useless to regret…

Anyway, the idea is by using DP. It is a modified version of traditional DP to find longest palindrome in a string with removable characters. Lets define the state like this : len[i][j] -> length of longest palindrome from node i to node j, and st[i][j] -> the longest palindrome itself from i to j. Then, for each of those states, there are 2 indexes, k and l, where path[i][k]==path[l][j], and we will try to check every possible pair of k and l (of course, k and l must be located between i and j), take the longest one (or if the length is the same, take the lexicographically smaller one). Then the answer will be in st[0][n-1]. Notice that it is impossible to have “No Palindromic Path”, since a string which consists of a single character is also a palindromic string. The complexity is about o(n^4).

Here is a sample code of mine  (sorry, it’s a lil’ bit messy code of mine ) :

#include<cstdio>
#include<string>
using namespace std;
string st[100][100],tmp;
int len[100][100],i,j,k,l,m,t,n;
char d[100][100],ch;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%c",&ch);
            for(j=0;j<n;j++){
                scanf("%c",&ch);
                len[i][j]=0;
                st[i][j]="";
                if(i>=j) continue;
                len[i][j]=1;
                st[i][j]+=ch;
                d[i][j]=ch;
            }
        }
        for(k=1;k<n;k++){
            for(i=0;i<n;i++){
                if(i+k>=n) break;
                j=i+k;
                for(l=i+1;l<j;l++){
                    for(m=l;m<j;m++){
                        if(d[i][l]==d[m][j]){
                            tmp=d[i][l]+st[l][m]+d[m][j];
                            if(len[l][m]+2>len[i][j]){
                                len[i][j]=len[l][m]+2;
                                st[i][j]=tmp;
                            }
                            else if(len[l][m]+2==len[i][j] && st[i][j]>tmp) st[i][j]=tmp;
                        }
                    }
                }
            }
        }
        printf("%s\n",st[0][n-1].c_str());
    }
}