ColorfulBuilding

作者： 权大磊

关键字： 动态规划 前缀和优化

题目描述

现有 $n$ 座房子排成一行， 编号为 $i$ 的房子高度为 $i$， 每座房子有一种颜色， 现给出两个字符串分别直接合并后得到 $c1$,$c2$， 当且只当 $c1[i] == c1[j]$ 并且 $c2[i] == c2[j]$ 时认为 $i$ 和 $j$ 两座房子颜色相同， 现在从左往右看问有多少种房子的排列， 可以使人看到 $L-1$ 种颜色变换$(L种颜色)$。

数据范围： $n ≤ 1296, L ≤ n$

时间限制：$2s$

空间限制: $64M$

题解

很容易想到用动态规划来解决这一问题， 为方便考虑， 我们将题目想成从小到大来填 $n$ 个空位， 定义 $f[i][j]$ 表示前 $i$ 个数看到 $j$ 种颜色 $(j-1种颜色变换)$ 时合法的排列个数。 枚举上一次看到的数是 $k$ ，那么第 $i$ 个数需要放在剩下的第一个空格处，否则后面更大的数放在这个空格时将会破坏原来的颜色变换，剩下 $i-p-1$ 个数在 $n - p - 1$ 个空格中任意选， 所以 $f[i][j] += f[k][?] * A( n-p-1, i-p-1 )$ 。 ($f[i][1]$特殊处理)

此时时间复杂度为 $n^3$， 用前缀和优化一下即可降为 $n^2$。