题目大意

给你个平面上的一堆点，问序列\({p_i}\)的个数。

满足\(y_{p_{i-1}}>y_{p_i}\)并且\(x_{p_i}\)在\(x_{p_i-1}\)和\(x_{p_i-2}\)之间。

---

正解

我不知道为什么我的树状数组打挂了……尽管不一定能AC，但是WA了……

这题的正解有很多，最为传奇的，则是彭大爷的神仙解法。

显然这是个DP，而他抛弃了按照\(y\)从大到小排序的传统做法，反而是以\(x\)从小到大排序。将\({p_i}\)倒过来做。设\(f_{i,0/1}\)表示到\(i\)这个点，上一个点在左边或者右边的方案数。

DP的时候\(i\)从左到右扫过去，然后从右到左枚举\(j\)，有两种转移：

如果\(y_j<y_i\)，则从\(f_{j,1}\)转移到\(f_{i,0}\)

如果\(y_j>y_i\)，则从\(f_{i,0}\)转移到\(f_{j,1}\)

这样的转移为什么是对的？实际上随便画个图就能理解了。

具体来说，在第一类转移的时候，很显然之前转移到\(f_{j,1}\)的是\(j\)和\(i\)之间的状态；

在第二类转移的时候，很显然之前转移到\(f_{i,0}\)的是\(j\)和\(i\)之间的状态。

这样就保证了题目要求的性质。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 7010inline int input(){    char ch=getchar();    while (ch<'0' || '9'
       
        =1;--j)            if (d[j].y
       
      
     
    

---

总结

这样的DP真是太鬼畜了……

彭大爷牛逼！！！

%%%