Description
二维平面上有 n 个点(xi, yi), 现在这些点中取若干点构成一个集合 S, 对它们按照 x 坐标排序, 顺次连接, 将会构成一些连续上升, 下降的折线, 设其数量为 f(S). 如下图中, 1->2,2->3,3->5,5->6(数字为下图中从左到右的点编号), 将折线分为了 4 部分, 每部分连续上升, 下降.
现给定 k, 求满足 f(S) = k 的 S 集合个数.
Input
第一行两个整数 n 和 k, 以下 n 行每行两个数 (xi, yi) 表示第 i 个点的坐标. 所有点的坐标值都在 [1, 100000] 内, 且不存在两个点, x 坐标值相等或 y 坐标值相等
Output
输出满足要求的方案总数 mod 100007 的结果
- Sample Input
- 5 1
- 5 5
- 3 2
- 4 4
- 2 3
- 1 1
- Sample Output
- 19
- HINT
对于 100% 的数据, n <= 50000,0 <k <= 10
基础的 $n^2k$ 的 dp 很好想, 然后你会发现每一个点的转移都是以所以 y 坐标小于或大于它的所有数为基础
这里可以用树状数组 / 线段树来优化转移,
代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #define M 100010
- #define mod 100007
- using namespace std;
- struct point{int x,y;}a[M];
- bool cmp1(point a1,point a2) {return a1.x<a2.x;}
- bool cmp2(point a1,point a2) {return a1.y<a2.y;}
- int ans,n,m;
- int f[M][11][2];
- struct change_query
- {
- int val[M];
- void insert(int loc,int v)
- {
- for(int i=loc;i<=n;i+=i&(-i))
- (val[i]+=v)%=mod;
- }
- int query(int loc)
- {
- int ans=0;
- for(int i=loc;i>0;i-=i&(-i)) (ans+=val[i])%=mod;
- return ans;
- }
- int get(int l,int r) {return (query(r)-query(l-1)+mod)%mod;}
- }T[11][2];
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
- sort(a+1,a+1+n,cmp2);
- for(int i=1;i<=n;i++) a[i].y=i;
- sort(a+1,a+1+n,cmp1);
- for(int i=1;i<=n;i++)
- {
- f[i][0][0]=f[i][0][1]=1;
- T[0][0].insert(a[i].y,f[i][0][0]);
- T[0][1].insert(a[i].y,f[i][0][1]);
- for(int k=1;k<=m;k++)
- {
- int y=a[i].y;
- if(y!=1)
- {
- (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];
- T[k][1].insert(y,f[i][k][1]);
- }
- if(y!=n)
- {
- (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];
- T[k][0].insert(y,f[i][k][0]);
- }
- }
- }
- for(int i=1;i<=n;i++) (ans+=f[i][m][0]+f[i][m][1])%=mod;
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2775392.html