题目详情 - [NOI2009] 管道取珠 - BZOJ by HydroOJ
-
非常神奇的一个思路。
-
考虑我们要计算的式子的真正意义。\(\sum a_i^2\) 不就相当于让两个管道取珠系统同时进行，最后取出方案完全相同的方案数吗？
-
因此我们考虑朴素 \(dp\) 两个管道是怎么取珠的。
-
设计状态：设 \(dp_{i,j,k,l}\) 表示第一个系统上面取到了 \(i\)，下面取到了 \(j\)。第二个分别取到 \(k,l\) 的方案数。
-
转移：
\[\begin{cases} dp_{i,j,k,l}\leftarrow dp_{i-1,j,k-1,l} & a_i=a_k \\ dp_{i,j,k,l}\leftarrow dp_{i-1,j,k,l-1} & a_i=b_l \\ dp_{i,j,k,l}\leftarrow dp_{i,j-1,k-1,l} & b_j=a_k \\ dp_{i,j,k,l}\leftarrow dp_{i,j-1,k,l-1} & b_j=b_l \\ \end{cases} \] -
优化：
-
发现有 \(i+j=k+l\)，可以优化掉一维
-
开三维空间开不下，可以滚动数组优化掉一维
-
-
-
最终复杂度 \(O(n^3)\)