【2018 国庆雅礼 NOIP 培训】D1T2 折射（refract）

发表于

这里是题面

首先，若我们将所有点按照 yi 的顺序转移, 有上界和下界两个限制, 难以优化。

容易想到按照 xi 排序转移, 并记录 fi,0/1 表示以第 i 个点为顶端接下来向 左或向右的折线方案数。

从左到右加点, 考虑前 i 个点构成的包含 i 点的折线。由于新点横坐标最大, 所以只可能在折线的第一位或第二位:

1. ∀yj</sub> < yi,fi,0 ← fj,1

2. ∀yj</sub> > yi,fj,1 ← fk,0 | xk > xj and yk < yi

第二种情况可以前缀和优化, 复杂度 O(n2),详情看代码吧。

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
#include <bits/stdc++.h>

using std::pair;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second

const int oo = 0x3f3f3f3f;

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int N = 6000;
const int mo = 1e9 + 7;

pii p[N + 5];
int dp[N + 5][2], n;

int main() {

    read(n);
    for(int i = 1; i <= n; i++) {
        read(p[i].fst), read(p[i].snd);
    }
    sort(p + 1, p + n + 1);

    for(int i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = 1;

        for(int j = i-1; j >= 1; j--) {
            if(p[j].snd > p[i].snd) {
                (dp[j][1] += dp[i][0]) %= mo;
            }else {
                (dp[i][0] += dp[j][1]) %= mo;
            }
        }
    }

    int ans = mo - n;
    for(int i = 1; i <= n; i++) ans = ((ans + dp[i][0]) % mo + dp[i][1]) % mo;
    printf("%d\n", ans);

    return 0;
}