二维平面上有n个点(xi, yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。
现给定k，求满足f(S) = k的S集合个数。
二维平面上有n个点(xi, yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。
现给定k，求满足f(S) = k的S集合个数。
第一行两个整数n和k，以下n行每行两个数(xi, yi)表示第i个点的坐标。所有点的坐标值都在[1, 100000]内，且不存在两个点，x坐标值相等或y坐标值相等
输出满足要求的方案总数 mod 100007的结果
对于100%的数据，n <= 50000，0 < k <= 10
基础的$n^2k$的dp很好想，然后你会发现每一个点的转移都是以所以y坐标小于或大于它的所有数为基础
这里可以用树状数组/线段树来优化转移、
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define M 100010 5 #define mod 100007 6 using namespace std; 7 struct point{int x,y;}a[M]; 8 bool cmp1(point a1,point a2) {return a1.x<a2.x;} 9 bool cmp2(point a1,point a2) {return a1.y<a2.y;} 10 int ans,n,m; 11 int f[M][11][2]; 12 struct change_query 13 { 14 int val[M]; 15 void insert(int loc,int v) 16 { 17 for(int i=loc;i<=n;i+=i&(-i)) 18 (val[i]+=v)%=mod; 19 } 20 int query(int loc) 21 { 22 int ans=0; 23 for(int i=loc;i>0;i-=i&(-i)) (ans+=val[i])%=mod; 24 return ans; 25 } 26 int get(int l,int r) {return (query(r)-query(l-1)+mod)%mod;} 27 }T[11][2]; 28 int main() 29 { 30 scanf("%d%d",&n,&m); 31 for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); 32 sort(a+1,a+1+n,cmp2); 33 for(int i=1;i<=n;i++) a[i].y=i; 34 sort(a+1,a+1+n,cmp1); 35 for(int i=1;i<=n;i++) 36 { 37 f[i][0][0]=f[i][0][1]=1; 38 T[0][0].insert(a[i].y,f[i][0][0]); 39 T[0][1].insert(a[i].y,f[i][0][1]); 40 for(int k=1;k<=m;k++) 41 { 42 int y=a[i].y; 43 if(y!=1) 44 { 45 (f[i][k][1]+=T[k][1].get(1,y-1)+T[k-1][0].get(1,y-1))%=mod;//f[i][k][1]+=f[j][k][1]+f[j][k-1][0]; 46 T[k][1].insert(y,f[i][k][1]); 47 } 48 if(y!=n) 49 { 50 (f[i][k][0]+=T[k][0].get(y+1,n)+T[k-1][1].get(y+1,n))%=mod;//f[i][k][0]+=f[j][k][0]+f[j][k-1][1]; 51 T[k][0].insert(y,f[i][k][0]); 52 } 53 } 54 } 55 for(int i=1;i<=n;i++) (ans+=f[i][m][0]+f[i][m][1])%=mod; 56 printf("%d",ans); 57 return 0; 58 }
原文：https://www.cnblogs.com/Slrslr/p/9684063.html