void LP(const string &str, int **c)
{
    int m = str.size();
    for(int i=0; i<m; ++i)
        c[i][i] = 1;
    for(int d=1; d<m; ++d)
    { // 自底向上
        for(int i=0; i<m-d; ++i)
        {
            int j = i + d;
            if(str[i] == str[j] && i+1 == j)
                c[i][j] = 2;
            else if(str[i] == str[j] && i+1 != j)
                c[i][j] = c[i+1][j-1]+2;
            else
                c[i][j] = max(c[i][j-1], c[i+1][j]);
        }
    }
}