滚动数组优化二维dp

如题所示要我们求的是最长可能的取模合并后相同的字符串长度考虑到合并操作本身满足结合律而且合并顺序不影响故可以建立前缀和数组代表i-n的合并取模数这个题可以转化为对ab字符串分别分块使得每一块的数值取模相等如果我们可以把它当作前缀和数组的差分按块分Pa[i]-Pa[i-1]Pb[i]-Pb[i-1],最左边的边界都是0就需要每块相等可以推出每个Pa[i]Pb[i],依据这个相当于找位置严格递增的元素相等的序列二维dp就是dp[i][j]代表a串i之前、b串j之前的方案数量状态转移方程为通过滚动数组进行优化可以存一个数作为dp[i-1][j],更新之后就是左上角的方格而dp[i-1][j]是旧数组dp[i][j-1]是左边已经处理过的数组代码如下#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cint; while(t--) { string a,b; cinab; int asa.size(),bsb.size(); vectorint pa(as2),pb(bs2); for(int i0;ias;i)pa[i1](pa[i](ias?0:a[i]-0))%10; for(int i0;ibs;i)pb[i1](pb[i](ibs?0:b[i]-0))%10; vectorint dp(as2,0); if(pa[as]!pb[bs]) { cout-1\n; continue; } for(int i0;ibs;i) { int ini0; for(int j0;jas;j) { int olddp[j]; if(pa[j]pb[i]) { dp[j]ini1; } else { int left(j0?0:dp[j-1]); dp[j]max(dp[j],left); } iniold; } } coutdp[as-1]\n; } }