题目详情 - [cqoi2013]二进制a+b - BZOJ by HydroOJ
-
起初想的按位贪心，后来发现不太可行，或者说按位贪心是不必要的(就像对于可以直接求出答案的做法进行二分答案一样)
-
我们直接考虑数位 dp
-
状态设计：设 \(dp_{i,j,k,l,0/1}\) 表示前 \(i\) 个数， \(a\) 用了 \(j\) 个 \(1\) ，\(b\) 用了 \(k\) 个 \(1\) ，\(c\) 用了 \(l\) 个 \(1\) ，对下一位有没有进位的最小的 \(c\)
-
初始化： \(dp_{i,j,k,l,0/1} \leftarrow \infty,dp_{0,0,0,0,0}\leftarrow 0\)
-
转移：显然，还是算了
-
-
最终复杂度 \(O(\log n^4)\)