首页 > 其他 > 详细

[BZOJ2688]折线统计

时间:2018-09-21 00:22:28      阅读:184      评论:0      收藏:0      [点我收藏+]

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坐标小于或大于它的所有数为基础

这里可以用树状数组/线段树来优化转移、

代码:

 

 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 }

 

[BZOJ2688]折线统计

原文:https://www.cnblogs.com/Slrslr/p/9684063.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!