本文主要是介绍摩天楼 DP优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有N（≤1300）栋摩天楼，从左往右排成一行。第i栋的高度是i个单位，并且每栋摩天楼都有颜色（有些摩天楼的颜色相同），将这些摩天楼排列，有多少种排列的方法，使得从左往右看去，看到不多不少刚好L栋摩天楼，答案mod 1000000009。
这里定义一下“看到”，首先若某栋摩天楼左边有比它高的，那就看不到。如果从左往右依次连续看到的两栋（或以上）摩天楼颜色相同，会误认为是一栋。
由于这个关系到次序问题，所以DP的顺序可以按照从大到小的顺序来，这里只需要把读入的顺序倒过来（读入是从小到大，下面的描述第i栋的高度是n - i + 1）。
记f（j，i）为能够看到j栋摩天楼，并且放置了前i栋摩天楼后，第一栋看到的楼就是第i栋楼。求出f（j，i）需要枚举前一栋看到的楼是什么，假设看到的是k这栋楼：
如果k和i的颜色是一样的，那么会误当成一栋，同时k + 1至i - 1这些楼需要放在k的后面，因为它们都比k矮，那么前一栋看到的就不是k了，那么，k + 1至i - 1这些楼放置的方案数为（假设下标为1），k * （k + 1） * （k + 2） * … * （k + i - 2），若k + 2 等于 i，那么就什么都不用乘，因为i,k之间没有其他楼：f（j，i） += f（j，k） * k * （k + 1） * （k + 2） * … * （k + i - 2）；
如果颜色不一样，那么就能多看到一栋楼：f（j，i） += f（j - 1，k） * k * （k + 1） * （k + 2） * … * （k + i - 2）。
时间复杂度：首先n^2种状态，转移O（n），总为O（n^3）。
我们需要再优化一下转移，可以画个表格来寻找方法：
摩天楼1,3,6是同一种颜色，而1,3,5,6中没有一个的颜色和摩天楼7相同，它们的颜色也不一定相同。现在若需要求f（3，7）（蓝色部分），它的值等于：
f（3, 7） =
+ f（2, 1） * 1 * 2 * 3 * 4 * 5
+ f（3, 2） * 2 * 3 * 4 * 5
+ f（2, 3） * 3 * 4 * 5
+ f（3, 4） * 4 * 5
+ f（2, 5） * 5
+ f（2, 6）
把它分成黄色，绿色，蓝色三个部分求解。
再来看看它前一个同种颜色的摩天楼（第4栋）：
f（3, 4） =
+ f（2, 1） * 1 * 2 * 3
+ f（3, 2） * 2 * 3
+ f（2, 3） * 3
看到没有，f（3， 7）划线部分的值和f（3， 4）是一样的。并且加粗部分是划线部分的4 * 5倍，黄色部分的值就求出来了！至于i * （i + 1）* … * j，可以预处理。然后，f（3, 4） * 4 * 5可以单独算（绿色部分）。接着，就剩下f（2, 5） * 5 + f（2, 6）。既然第4栋摩天楼是前一个和7同颜色的，那么，4 + 1至7 - 1的楼都不和7相同颜色，这就可以用类似于部分和的东西。
由于公式编辑麻烦，这里就不贴了，找找规律就知道了。
那么g（2， 6） =
+ f（2, 1） * 1 * 2 * 3 * 4 * 5
+ f（2, 2） * 2 * 3 * 4 * 5
+ f（2, 3） * 3 * 4 * 5
+ f（2, 4） * 4 * 5
+ f（2, 5） * 5
+ f（2, 6）
g（2， 4） =
+ f（2, 1） * 1 * 2 * 3
+ f（2, 2） * 2 * 3
+ f（2, 3） * 3
+ f（2, 4）
那么我们所需要求的f（2, 5） * 5 + f（2, 6）就等于g（2， 6）减去4 * 5倍的g（2， 4）（橙色部分）。至于g如何求，这应该很简单吧。g（j，i） = g（j，i-1） * i + f（j， i）。
这样，我们就可以O(1)实现求解某个f（j， i）了。问题就到此结束了，时间复杂度就是O(n^2)。
我的代码下标是从0开始的，写的一般般：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;const ll mod = 1000000009;
const int N = 1300, C = 2707;char x[N];
int n, L, col[N]; // 第i栋楼的颜色编号
int pre[C]; // pre[col]，前一个颜色为col的摩天楼的标号
ll f[N][N], // 即所说的f数组 fac[N][N], // fac(i, j) 用来保存 i * （i + 1）* … * j sum[N]; // 即所说的g数组，这里省去了一维 inline int ord(char a)
{if (a >= 'a' && a <= 'z') return (int) a - 'a';if (a >= 'A' && a <= 'Z') return (int) a - 'A' + 26;
}int main()
{freopen("sky.in", "r", stdin);freopen("sky.out", "w", stdout);scanf("%d%d\n", &n, &L);scanf("%s\n", x);for (int i = 0; i < n; i ++){char ch;scanf("%c", &ch);// 题目要求的颜色读入方式是两个字母col[i] = ord(x[i]) * (26 << 1) + ord(ch);}// 加个哨兵，方便输出 col[n] = C - 1;// 把摩天楼的顺序调转 for (int i = 0; i < n >> 1; i ++) swap(col[i], col[n - i - 1]);for (int i = 0; i <= n + 1; i ++)for (int j = 0; j <= n + 1; j ++) fac[i][j] = 1LL;for (int i = 1; i <= n; i ++){fac[i][i] = i;for (int j = i + 1; j <= n; j ++)fac[i][j] = (fac[i][j - 1] * j) % mod;}for (int j = 1; j <= L + 1; j ++){for (int i = 0; i <= n; i ++) pre[col[i]] = -1;if (j == 1) f[j][0] = 1LL; pre[col[0]] = 0;sum[0] = f[j - 1][0];for (int i = 1; i <= n; i ++){if (pre[col[i]] == -1) f[j][i] = sum[i - 1];else {int p = pre[col[i]];if (p > 0)f[j][i] = f[j][p] * fac[p][i - 1] % mod;f[j][i] = (f[j][i] + f[j][p] * fac[p + 1][i - 1]) % mod;if (p + 1 < i) f[j][i] = (f[j][i] + sum[i - 1] - sum[p] * fac[p + 1][i - 1] % mod + mod) % mod;}pre[col[i]] = i;sum[i] = (sum[i - 1] * i + f[j - 1][i]) % mod;}}printf("%I64d\n", f[L + 1][n]);return 0;
}
这篇关于摩天楼 DP优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
