题目
题目大意
有高为\(1, 2,
3,···,n\)的杆子各一根排成一行, 从左边能看到\(l\)根, 从右边能看到\(r\)根, 求有多少种可能。
题解
因为所有杆子的高度都不一样, 我们假设\(2\)\(i\)所有杆子已经安排上了~放好了(每次只考虑最矮的一根),
那么有三种情况: 1. 放在最左边, 只能从左边看到它 2. 放在最右边,
只能从右边看到它 3. 放在中间, 两边都看不到它, 因为中间有\(i - 2\)个位置可以放, 因此有\(i - 2\)种情况
依次可以得到状态转移方程:
\[d(i, j, k) = d(i - 1, j - 1, k) + d(i -
1, j, k - 1) + d(i - 1, j, k) * (i - 2) \]
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <cstdio>
unsigned long long dp[30][30][30];
int T, n, l, r;
int main(int argc, char const *argv[]) {
dp[1][1][1] = 1;
for (register unsigned long long i(2); i <= 20; ++i) {
for (register unsigned long long j(1); j <= i; ++j) {
for (register unsigned long long k(1); k <= i; ++k) {
dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2);
}
}
}
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &l, &r);
printf("%llu\n", dp[n][l][r]);
}
return 0;
}
|