$des$

小 $Y$ 十分喜爱光学相关的问题, 一天他正在研究折射.

他在平面上放置了 $n$ 个折射装置, 希望利用这些装置画出美丽的折线.

折线将从某个装置出发, 并且在经过一处装置时可以转向, 若经过的装置坐

标依次为 $(x_1, y_1), (x_2, y_2) ... (x_k, y_k ),$ 则必须满足:

$\bullet \forall j \in (1, k], y_j < y_{j - 1}$

$\bullet \forall j \in (2, k], x_{j - 2} < x_{j} < x_{j - 1} 或者 x_{j - 1} < x_j < x_{j - 2}$

求不同种的画法

$sol$

按 $x$ 坐标排序，$f_{i, 0/1}$ 表示以第 $i$ 个点为顶端下来向左或向右的折线的方案数

从左到右加点，考虑前 $i$ 个点构成的包含 $i$ 点的折线，由于新点横坐标最大, 所以只可能在折线的

第一位或第二位：

1. $\forall y_j < y_i, f_{i, 0} \gets f_{j, 1}$

2. $\forall y_j > y_i, f_{j, 1} \gets f_{k, 0} | x_k > x_j 且 y_k < y_i$

第二种情况可以前缀和优化, 复杂度 $O(n^2)$

$code$

#include 
     
      using std::pair;typedef long long ll;typedef pair
      
        pii;#define fst first#define snd secondconst int oo = 0x3f3f3f3f;#define gc getchar()inline int read() {    int x = 0; char c = gc;    while(c < '0' || c > '9') c = gc;    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;    return x;}const int N = 6000;const int mo = 1e9 + 7;pii p[N + 5];int dp[N + 5][2], n;int main() {    n = read();    for(int i = 1; i <= n; i++) p[i].fst = read(), p[i].snd = read();    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;    std:: cout << ans;    return 0;}