划分LCS最长公共子序列思路把合并看成划分因为只要定了划分的段的情况段内的结合顺序就没影响了再次转化pret和pres相等的点可以看成是划分的点因为默认了上一个公共点是相同的就成功转化成了LCS最长公共子序列问题代码如下void solve(){ string s,t;cinst; int ns.size(),mt.size(); s s; t t; vectorintpres(n10),pret(m10); vectorvectorint dp(n10,vectorint(m10)); for(int i1;in;i) pres[i](pres[i-1](s[i]-0))%10; for(int i1;im;i) pret[i](pret[i-1](t[i]-0))%10; if(pres[n]!pret[m]){ cout-1endl; return; } for(int i1;in;i){ for(int j1;jm;j){ dp[i][j]max(dp[i][j-1],dp[i-1][j]); if(pres[i]pret[j]){ dp[i][j]max(dp[i][j],dp[i-1][j-1]1); } } } coutdp[n][m]endl; }