Luogu 3255 - [JLOI2013]地形生成

还是一道很不错的计数题目。

对于第一问是可以不进行 $\operatorname{DP}$ 的:考虑将山从大到小构建答案数列的过程,发现对于任意高度较其高的山可以视作相同的山,将他们看作一个暂时构造完成的数列。把这座山加入,无非是进行放置空位的选择,再考虑上关键值的限制,其对答案的贡献应为:

其中,$\operatorname{sum}$ 为高度与此山相同的山的数目。

分析第二问,对于高度相同的山仍然可以按照第一问处理,只是高度相同的山加入序列时会产生重复贡献的情况,同时因为关键值的存在而不能直接计算。针对高度相同分别处理,考虑 $\operatorname{DP}$ ,设 $f_{i, j}$ 为在将 $i$ 座山,插入前 $j$ 个空的方案数:

很好理解的 $\operatorname{DP}$ ,可以简化使复杂度正确:

复杂度 $O(n^2)$ 。

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
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>

#define MAXN 1005

using namespace std;

const int mod = 2011;
int n;
int f[MAXN];

struct node {
int h, k;
node(int h = 0, int k = 0):h(h), k(k) {}
}a[MAXN];

int read() {
char c = getchar();
int x = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}

bool comp(node a, node b) {
return a.h > b.h || (a.h == b.h && a.k < b.k);
}

int solve1() {
int sum = 0, ans = 1;
for (int i = 1; i <= n; ++i) {
if (a[i].h == a[i - 1].h)
++sum;
else
sum = 0;
ans = ans * min(i, a[i].k + sum) % mod;
}
return ans;
}

int solve2() {
int ans = 1;
for (int i = 1; i <= n; ++i) {
int j = i;
while (a[j + 1].h == a[j].h)
++j;
memset(f, 0, sizeof(f));
f[0] = 1;
for (int p = i; p <= j; ++p)
for (int q = 1; q <= min(a[p].k, i) - 1; ++q)
f[q] = (f[q - 1] + f[q]) % mod;
int sum = 0;
for (int l = 0; l <= min(a[j].k, i) - 1; ++l)
sum = (sum + f[l]) % mod;
ans = ans * sum % mod;
swap(i, j);
}
return ans;
}

int main() {
n = read();
for (int i = 1; i <= n; ++i) {
a[i].h = read();
a[i].k = read();
}
sort(a + 1, a + n + 1, comp);
printf("%d %d\n", solve1(), solve2());
}