非常简单

我们首先不考虑转换规则，来推导最长回文子序列的状态转移方程。

当我们定义f[i][j]为i-j内的最长回文子序列时则可以思考：

当a[i]=a[j]的时候,则f[i][j]=f[i-1][j+1]+2;

当a[i]!=a[j]的时候,则f[i][j]=max(f[i][j-1],f[i+1][j]);

状态转移方程写好了，接下来就该考虑转换规则了。

当我们知道,任意一个\(x\)可以转化为\(y\),那么我们可以将x与y联通,亦无大碍.所以我们先将所有\(x\)转化为\(y\),以此类推,我们将所有可转换的\(x\)全转换为\(y\),此解一定为为最优解,读者可自己进行简单证明,在此我不赘述。

于是将每组\(x\) \(y\)联通之后,你想到了什么?没错！并查集可以很好的解决这个问题.在输入每一个a[i],对a[i]进行getf操作.再对其进行动态规划,这题就这么简单了.

代码就不放了

算了,我还是放个部分代码吧.

并查集部分代码:

    int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}

区间DP部分代码:

    if (a[i]==a[j])f[i][j]=f[i+1][j-1]+2;
    else f[i][j]=max(f[i][j-1],f[i+1][j]);

其余请自己写.