Educational Codeforces Round 192 (Rated for Div. 2)D（前缀和+LCS）

划分+LCS（最长公共子序列）

思路：

把合并看成划分，因为只要定了划分的段的情况，段内的结合顺序就没影响了

再次转化，pret和pres相等的点可以看成是划分的点，因为默认了上一个公共点是相同的

就成功转化成了LCS最长公共子序列问题
代码如下：

void solve(){ string s,t;cin>>s>>t; int n=s.size(),m=t.size(); s=" "+s; t=" "+t; vector<int>pres(n+10),pret(m+10); vector<vector<int> >dp(n+10,vector<int>(m+10)); for(int i=1;i<=n;i++) pres[i]=(pres[i-1]+(s[i]-'0'))%10; for(int i=1;i<=m;i++) pret[i]=(pret[i-1]+(t[i]-'0'))%10; if(pres[n]!=pret[m]){ cout<<-1<<endl; return; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;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); } } } cout<<dp[n][m]<<endl; }