NOIP模拟（10.22）T2 杆子的排列

本文主要是介绍NOIP模拟（10.22）T2 杆子的排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

杆子的排列

题目背景：

10.22 NOIP模拟作业T2

分析：DP

定义状态dp[i][j][k]表示，目前枚举到第i大的数（即n - i + 1）那么显然如果这一个数放在左边，可以在左边被看到，放在右边可以在右边看到，放在中间任何位置都不能被看见，（也就是说当前枚举的数是目前最小的一个）那么转移就很显然了

dp[i][j][k] = (dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i -1][j][k] * (i - 2))

dp[i - 1][j - 1][k] à 这一个放在最左边

dp[i - 1][j][k - 1] à 这一个放在最右边

dp[i - 1][j][k] à 这一个放在中间，（一共有i - 1个，中间位置有i - 2个）

上面的DP是O(n³)的，那么总复杂度是O(n³+ T)

然而，刚才又知道了一种也很妙妙的方法，dp[i][j]表示，当前枚举到第i大的数，然后左边的上升序列长度为j的方案数，显然，右边的上升序列长度为j的方案数也是dp[i][j]，那么对于每一个n，我们枚举最高的杆子n所在的位置x，然后在剩下的n - 1个书中选择x - 1个放在左边，并且上升序列为l - 1，然后右边的n - x个数满足上升序列为r - 1那么显然方案数位dp[x - 1][l - 1] *dp[n - x][r - 1] * c(n - 1, x - 1)，(c为组合数)，那么我们就可以在O(n²+ Tn)的时间里面解决了（是不是可以该数据范围啊，T = 1000000, n =200或者T = 1000, n = 1000呵呵哒）

 

O(n³ + T)

Source：

/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>const int MAXN = 200 + 10;
const int mod = 998244353;int n, l, r, t;
int dp[MAXN][MAXN][MAXN];inline void add(int &x, int t) {x += t, (x >= mod) ? (x -= mod) : (0); 
}inline void pre_work() {dp[1][1][1] = 1;for (int i = 2; i < MAXN; ++i)for (int j = 1; j < MAXN; ++j)for (int k = 1; k < MAXN; ++k) {if (j + k > i + 1) break ;if (j + k < 3) continue ;add(dp[i][j][k], dp[i - 1][j - 1][k]);add(dp[i][j][k], dp[i - 1][j][k - 1]);add(dp[i][j][k], (long long)dp[i - 1][j][k] * (i - 2) % mod);}
//	for (int i = 1; i <= 5; ++i)
//		for (int j = 1; j <= 5; ++j)
//			for (int k = 1; k <= 5; ++k)
//				std::cout << i << " " << j << " " << k << " " 
//					<< dp[i][j][k] << '\n'; 
}int main() {scanf("%d", &t), pre_work();while (t--) scanf("%d%d%d", &n, &l, &r), printf("%d\n", dp[n][l][r]);return 0;
}

O(n² + Tn)

Source：

/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>const int MAXN = 200 + 10;
const int mod = 998244353;int n, l, r, t, ans;
int dp[MAXN][MAXN], c[MAXN][MAXN];inline void add(int &x, int t) {x += t, (x >= mod) ? (x -= mod) : (0); 
}inline void pre_work() {dp[0][0] = 1;for (int i = 1; i < MAXN; ++i)for (int j = 1; j <= i; ++j) {add(dp[i][j], dp[i - 1][j - 1]);if (i > j) add(dp[i][j], (long long)dp[i - 1][j] * (i - 1) % mod);}
//	for (int i = 1; i <= 4; ++i)
//		for (int j = 1; j <= 4; ++j)
//			std::cout << i << " " << j << " " << dp[i][j] << '\n';for (int i = 0; i < MAXN; ++i) c[i][i] = 1, c[i][0] = 1;for (int i = 2; i < MAXN; ++i)for (int j = 1; j < i; ++j)c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
//	for (int i = 1; i <= 5; ++i)
//		for (int j = 1; j <= 5; ++j)
//			for (int k = 1; k <= 5; ++k)
//				std::cout << i << " " << j << " " << k << " " 
//					<< dp[i][j][k] << '\n'; 
}int main() {scanf("%d", &t), pre_work();while (t--) {scanf("%d%d%d", &n, &l, &r), ans = 0;for (int i = 0; i <= n - 1; ++i)add(ans, (long long)dp[i][l - 1] * (long long)dp[n - 1 - i][r - 1] % mod * (long long)c[n - 1][i] % mod);printf("%d\n", ans);}return 0;
}

这篇关于NOIP模拟（10.22）T2 杆子的排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---