Culture Code

题目描述

There are famous Russian nesting dolls named matryoshkas sold in one of the souvenir stores nearby, and you’d like to buy several of them. The store has n different matryoshkas. Any matryoshka is a figure of volume outi with an empty space inside of volume ini (of course, outi>ini).

You don’t have much free space inside your bag, but, fortunately, you know that matryoshkas can be nested one inside another. Formally, let’s call a set of matryoshkas nested if we can rearrange dolls in such a way, that the first doll can be nested inside the second one, the second doll — inside the third one and so on. Matryoshka i can be nested inside matryoshka j if outi≤inj. So only the last doll will take space inside your bag.

Let’s call extra space of a nested set of dolls as a total volume of empty space inside this structure. Obviously, it’s equal to , where are the indices of the chosen dolls in the order they are nested in each other.

Finally, let’s call a nested subset of the given sequence as big enough if there isn’t any doll from the sequence that can be added to the nested subset without breaking its nested property.

You want to buy many matryoshkas, so you should choose a big enough nested subset to buy it. But you will be disappointed if too much space in your bag will be wasted, so you want to choose a big enough subset so that its extra space is minimum possible among all big enough subsets. Now you wonder, how many different nested subsets meet these conditions (they are big enough, and there is no big enough subset such that its extra space is less than the extra space of the chosen subset). Two subsets are considered different if there exists at least one index i such that one of the subsets contains the i-th doll, and another subset doesn’t.

Since the answer can be large, print it modulo 10^{9}+7.

思路

计数问题想DP。如果一个套娃可以被套在另一个套娃内,我们就可以在两个点之间连上一条有向边,代价为内体积与外体积之差(这样一条边的代价就为额外空间的值了),问题转化为了最短路计数。问题在于我们无法对如此多的套娃每一个都进行判断,不过我们可以发现:如果套娃i可以被放进套娃j,且套娃j可以被放进套娃k(严格来说:),那么套娃i一定可以被放在套娃k中。那么我们不妨只在套娃i和最小那个可以套下套娃i的套娃之间建边(可以二分找到),代价为外体积与内体积之差;并且在内体积大小相邻的两个套娃之间建边,代价为两个内体积之差(这样如果我需要跳过中间的某个套娃时,就可以选择走这条边,中间的套娃的体积会被差分消去),这时再进行最短路计数即可(此时拓扑序和我们对in数组排序后的顺序已经相同)。

注意统计结果时只统计终点的结果,一个点如果是终点(也就是说它是最外层的套娃),那么没有哪个其他的套娃可以把它套进去(如果还有套娃可以容纳它,就不满足题目中足够大的前提)。

代码实现

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
80
81

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

typedef long long lint;
typedef std::pair<int, lint> edge;

struct doll {
int in, out;

bool operator< (const doll& d) const {
return in < d.in;
}
};

const size_t max_count = 200005;
const lint mod = 1e9 + 7;

doll list[max_count];
std::vector<edge> graph[max_count];

int in_copy[max_count];
lint distance[max_count], dp[max_count];

int main() {
int count;
std::cin >> count;

for (int i = 1; i <= count; i++) {
scanf("%d%d", &list[i].out, &list[i].in);
}

std::sort(list + 1, list + count + 1);

for (int i = 1; i <= count; i++) {
graph[i - 1].push_back(edge(i, list[i].in - list[i - 1].in));
in_copy[i] = list[i].in;
}

for (int i = 1; i <= count; i++) {
int out = list[i].out;
int next = std::lower_bound(in_copy + i + 1, in_copy + count + 1, out) - in_copy;
graph[i].push_back(edge(next, list[next].in - list[i].out));
}

std::fill(distance, distance + count + 1, 1e16);
distance[0] = 0; dp[0] = 1;

for (int i = 0; i <= count; i++) {
for (int j = 0; j < graph[i].size(); j++) {
edge e = graph[i][j];
if (distance[e.first] > distance[i] + e.second) {
distance[e.first] = distance[i] + e.second;
dp[e.first] = dp[i];
}
else if (distance[e.first] == distance[i] + e.second) {
dp[e.first] = (dp[e.first] + dp[i]) % mod;
}
}
}


lint min = 1e16;
for (int i = 1; i <= count; i++) {
if (list[i].out > list[count].in) {
min = std::min(min, distance[i]);
}
}

lint res = 0;
for (int i = 1; i <= count; i++) {
if (distance[i] == min && list[i].out > list[count].in) {
res = (res + dp[i]) % mod;
}
}

std::cout << res << std::endl;
return 0;
}