挺有趣的一道 $dp$，两问实际上就相当于是第一问是第二问的部分分
第一问
一开始以为要 $dp$，然而并不用
对于这种高度然后求方案数的题，可以只考虑其相对位置，因为只要所有相对位置确定了，那么整个序列就唯一确定了
首先肯定要先将它们以高度为第一关键字（由大到小），关键值为第二关键字（从小到大）排序
那么对于第 $i$ 座山，它就会有 $\min (i, key_i)$ 个相对位置可以占，因为有相同高度的山峰，所以还会多出 $same$ （$i$ 前面与其高度相同的山峰的个数）个位置
那么 $ans_1 = \prod\limits_{i = 1}^n min (i, key_i + same)$
第二问
症结还是在于相同高度的山峰会产生重复
但是显然如果一次性确定好所有相同山峰的位置是不会产生重复的，故考虑将每一组相同高度的山峰放在一起处理
为了避免重复，需要强制令这些相同高度的山峰放置有序，即后放的一定在先放的后面，那么就可以令 $f_{i, j}$ 表示（当前组相同高度山峰）前 $i$ 个放在前 $j$ 个位置上，并且第 $i$ 放在第 $j$ 个位置的方案数，则有（下示方程表示区间 $[l, r]$ 的相同高度山峰组）
$$
\begin{aligned}
f_{i, j} &= \sum\limits_{k = 1}^j f_{i - 1, k} (j \in [0, \min (l, key_i) - 1]) \\
&= f_{i - 1, j} + f_{i, j - 1}
\end{aligned}
$$
然后实际上第一维是没用的，再省掉就行了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 2011
using namespace std;
typedef long long LL;
const int MAXN = 1000 + 10;
LL f[MAXN]= {0};
struct hillSt {
int high;
int key;
hillSt (int fhigh = 0, int fkey = 0) :
high (fhigh), key (fkey) {}
bool operator < (const hillSt& p) const {
if (high == p.high)
return key < p.key;
return high > p.high;
}
} ;
int N;
hillSt hill[MAXN];
int getnum () {
int num = 0;
char ch = getchar ();
while (! isdigit (ch))
ch = getchar ();
while (isdigit (ch))
num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
return num;
}
int main () {
N = getnum ();
for (int i = 1; i <= N; i ++)
hill[i].high = getnum (), hill[i].key = getnum ();
sort (hill + 1, hill + N + 1);
LL ans1 = 1;
int same = 0;
for (int i = 1; i <= N; i ++) {
hill[i].high == hill[i - 1].high ? same ++ : same = 0;
ans1 = ans1 * 1ll * min (i, hill[i].key + same) % MOD;
}
LL ans2 = 1;
for (int l = 1; l <= N; l ++) {
int r;
for (r = l; r <= N && hill[r + 1].high == hill[r].high; r ++);
memset (f, 0, sizeof (f));
f[0] = 1;
for (int i = l; i <= r; i ++)
for (int j = 1; j <= min (l, hill[i].key) - 1; j ++)
f[j] = (f[j - 1] + f[j]) % MOD;
LL total = 0;
for (int j = 0; j <= min (l, hill[r].key) - 1; j ++)
total = (total + f[j]) % MOD;
ans2 = ans2 * total % MOD;
swap (l, r);
}
cout << ans1 << ' ' << ans2 << endl;
return 0;
}
|
