CF1383E Strange Operation-526互联

首先可以发现对于一次操作，本质上就是删掉存在于两个 \(1\) 之间的若干个 \(0\) 的其中一个或者删掉两个连续的 \(1\) 的其中一个。所以对于最终的 \(01\) 串 \(A\) ，令 \(B\) 表示 \(A\) 中两个 \(1\) 之间的 \(0\) 的个数，为了方便后面的计算，对于 \(A\) 以 \(1\) 开头或结尾，需要在 \(B\) 的开头或结尾补 \(0\) ，比如 \(A=1001\)，那么 \(B=\{0,2,0\}\) 。所以现在操作就相当于可以对 \(B\) 中的任意一个不为 \(0\) 的数字减 \(1\) ，或者删掉一个不处在开头结尾的 \(0\) ，这两个操作分别对应原来的删 \(0\) 和删 \(1\) 操作。
因为开头结尾不会被删除，所以可以先单独算出这部分对答案的贡献，也就是 \((B_1+1)\times(B_{|B|}+1)\) 。那么现在可以忽略开头结尾后的方案数乘上前面的式子就可以了，所以就可以认为整个 \(B\) 都可以进行减一和删零操作。
实际上一个原串 \(C\) 对应的 \(D\) 能变成 \(B\) ，当且仅当存在 \(1\le i_1\le...\le i_{|B|}\le |D|\)，\(B_{j}\le D_{i_j}\) 。这样就可以设 \(f_i\) 表示匹配到 \(D\) 第 \(i\) 的 \(B\) 的个数，然后转移时枚举 \(B\) 的上一位匹配到 \(D\) 的那一位就可以。但是需要继续优化，可以考虑对于一个 \(f_i\) 考虑它贡献到 \(f_j\) 的贡献是多少。因为一旦存在 \(k\) 满足 \(i<k<j\space,D_i<D_k\) 那么 \(f_i\) 一定不会转移到 \(f_j\) ，那么 \(f_i\) 对 \(f_j\) 的贡献就是 \(max\{0,D_j-max_{k=i+1}^{j-1} D_k\}\) 。