腾讯笔试——彩色楼房

妖狐艹你老母 2023-08-17 17:04 59阅读 0赞

# \# 彩色楼房 #

\\\[ Time Limit: 5000 ms \\quad Memory Limit: 262144 kB \\\]

### 题目 ###

小Q给你n个数1,2,3...n，代表n个楼，第i个楼的高度为i，**每个楼都有一个颜色**  
**现在将这些楼随机排列在一条直线上**，问有多少种排列方式，满足从最左边往右看（站在左边很远的地方看）能看到L-1次颜色的变变化，答案对1e9+9取模  
如果两个相同颜色楼的高度分别为H1，H2（H1<H2），H1在左边，且H1 H2之间的楼都比H1矮，那么站在左边来看就是一种颜色  
你能看到一个楼的前提是这个楼之前的楼都比它矮

#### input ####

第一行输入两个整数n，L（1<=n<=1296），（1<=L<=n）  
第二行输入n个整数Ci表示每个楼的颜色（1<=Ci<=n）

#### output ####

输出一个整数，代表方案数，并对1e9+9取模

## 思路 ##

以下做法参考厦大一位大佬...

### step1 ###

\\(O(N^3)\\) 暴力 \\(dp\\)，从后往前 \\(dp\\)。  
\\(dp\[i\]\[k\]\[j\]\\) 表示 到第 \\(i\\) 个楼房时，可以看到 \\(k\\) 个颜色，并且最左边楼层颜色为 \\(j\\)。  
对于 \\(dp\[i\]\[k\]\[j\]\\) 存在以下转移：

1.  首先考虑最左边的楼层是 \\(i\\) 后面的楼层，把 \\(i\\) 楼层插到后面去，那么有  
    \\\[ dp\[i\]\[k\]\[j\] = dp\[i+1\[k\]\[j\]\*(n-i) \\\]
2.  考虑最左边的楼层是 \\(i\\) 楼层，也就是当 \\(j==a\[i\]\\) 时，有  
    \\\[ dp\[i\]\[k\]\[j\] += dp\[i+1\]\[k\]\[j\] \\\\ dp\[i\]\[k\]\[j\] += dp\[i+1\]\[k-1\]\[\\sum\_\{j'=1\}^\{j' \\neq j\}j'\] \\\]  
    因为存在 \\(j' \\neq j\\) 的判断，在 \\(for\\) 一遍是很浪费时间的，所以可以开一个数组 \\(sum\\)，\\(sum\[i\]\[k\]\\) 表示 \\(\\sum\_\{j=1\}^\{j=n\}dp\[i\]\[k\]\[j\]\\)，然后用减法来得到答案。

时间复杂度 \\(O(N^3)\\)、空间复杂度\\(O(N^3)\\)  
代码：（这代码只能跑 \\(n\\) 在 \\(500\\) 以内)

void solve1() { mes(sum, 0); dp[n][1][a[n]] = 1; sum[n][1] = 1; for(int i=n-1; i>=1; i--) { for(int k=1; k<=m; k++) { for(int j=1; j<=n; j++) { if(j == a[i]) { dp[i][k][j] = (dp[i+1][k][j]*(n-i+1)%mod+sum[i+1][k-1]-dp[i+1][k-1][j])%mod+mod; dp[i][k][j] %= mod; } else { dp[i][k][j] = dp[i+1][k][j]*(n-i)%mod; } sum[i][k] = (sum[i][k] + dp[i][k][j])%mod; } } } printf("%lld\n", sum[1][m]); }

### step2 ###

通过观察式子不难发现，由于 \\(k\\) 只和 \\(k-1\\) 的答案有关，只要从大到小枚举 \\(k\\)，第一维是可以滚动优化掉。  
观察代码，我们发现第三层循环中，只有当 \\(j == a\[i\]\\) 时，转移比较复杂，对于其他的 \\(j\\)，转移过程完全一样。所以我们可以简化这层循环。  
首先把这层循环里的式子尽量提取出来。  
对于 \\(dp\\) 式子，可以直接计算 \\(j==a\[i\]\\) 的情况，把 \\(j \\neq a\[i\]\\) 的情况留在 \\(for\\) 中。这一步很容易做到。  
对于 \\(sum\\) 式子，可以发现\\(j \\neq a\[i\]\\)部分，\\(dp\\) 整体乘 \\(n-i\\)，所以这一部分可以写成 \\(sum\[k\]\*(n-i)-dp\[k\]\[j\]\*(n-i)\\)，然后在加上特别计算出的 \\(j==a\[i\]\\)的情况的 \\(dp\\) 值就可以了。  
时间复杂度\\(O(N^3)\\)，空间复杂度\\(O(N^2)\\)

void solve2() { mes(sum, 0); dp[1][a[n]] = 1; sum[1] = 1; for(int i=n-1; i>=1; i--) { for(int k=m; k>=1; k--) { { int j = a[i]; sum[k] = ((sum[k]*(n-i)%mod - dp[k][j]*(n-i)%mod)%mod+mod)%mod; dp[k][j] = (dp[k][j]*(n-i+1)%mod+sum[k-1]-dp[k-1][j])%mod+mod; dp[k][j] %= mod; sum[k] = (sum[k] + dp[k][j])%mod; } for(int j=1; j<=n; j++) { if(j != a[i]) { dp[k][j] = dp[k][j]*(n-i)%mod; } // printf("dp[%d][%d] = %lld\n", k, j, dp[k][j]); } } } printf("%lld\n", sum[m]); }

### step3 ###

还是在第三层循环上想办法，我们看到这一层除了\\(j==a\[i\]\\) 外都乘上了一个 \\((n-i)\\)，那么如果我们让 \\(j==a\[i\]\\) 时也乘上一个 \\((n-i)\\)，就可以统一整维的 \\(dp\\) 了。那么我们在保存的时候可以保存 \\(\\frac\{dp\[k\]\[j\]\}\{(n-i)\}\\) 的值，运算的时候在把这个原本应有的值乘回来就可以了。  
由于每一个 \\(i\\) 都要乘上一个 \\(\\frac\{1\}\{n-i\}\\)，也就是说在对于第 \\(i\\) 个楼房而言，一共乘上了 \\(\\frac\{1\}\{\\prod\_\{x=1\}^\{x\} n-x\}\\)  
这一步也可以做到，只要每次在运算 \\(j==a\[i\]\\) 时，让 \\(dp\[k\]\[j\]\\) 乘上他应该缩小的倍数就可以了。  
这样处理后，时间复杂度 \\(O(N^2)\\)，空间复杂度 \\(O(N^2)\\)

/*************************************************************** > File Name : a.cpp > Author : Jiaaaaaaaqi > Created Time : Tue 10 Sep 2019 10:21:23 PM CST ***************************************************************/ #include <map> #include <set> #include <list> #include <ctime> #include <cmath> #include <stack> #include <queue> #include <cfloat> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> #define lowbit(x) x & (-x) #define mes(a, b) memset(a, b, sizeof a) #define fi first #define se second #define pb push_back #define pii pair<int, int> typedef unsigned long long int ull; typedef long long int ll; const int maxn = 2e3 + 10; const int maxm = 1e5 + 10; const ll mod = 1e9 + 9; const ll INF = 1e18 + 100; const int inf = 0x3f3f3f3f; const double pi = acos(-1.0); const double eps = 1e-8; using namespace std; ll n, m; int cas, tol, T; ll sum[maxn]; ll dp[maxn][maxn]; ll a[maxn]; ll fpow(ll a, ll b) { ll ans = 1; while(b) { if(b&1) ans = ans*a%mod; a = a*a%mod; b >>= 1; } return ans; } int main() { // freopen("in", "r", stdin); scanf("%lld%lld", &n, &m); for(int i=1; i<=n; i++) { scanf("%lld", &a[i]); } mes(sum, 0); dp[1][a[n]] = 1; sum[1] = 1; ll base = 1; for(int i=n-1; i>=1; i--) { for(int k=m; k>=1; k--) { { int j = a[i]; sum[k] = ((sum[k]*(n-i)%mod - dp[k][j]*(n-i)%mod*base%mod)%mod+mod)%mod; dp[k][j] = ((dp[k][j]*base%mod*(n-i+1)%mod+sum[k-1])%mod-dp[k-1][j]*base%mod)%mod+mod; dp[k][j] %= mod; sum[k] = (sum[k] + dp[k][j])%mod; dp[k][j] = dp[k][j] * fpow(base*(n-i)%mod, mod-2)%mod; // printf("dp[%d][%d] = %lld\n", k, j, dp[k][j]*base); } } base = base*(n-i)%mod; } printf("%lld\n", sum[m]%mod); return 0; }

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/11504103.html