本文共 2388 字，大约阅读时间需要 7 分钟。

折线统计

题目链接：

题目大意

在一个图上有一些点，保证任意两个点的横纵坐标都不相同。

要你选一些集合，按 x 坐标排序依次连接，会构成一些连续上升下降的折线，问你折线数量是 k 条的有多少个集合满足。 数量对 100007 取模。

思路

这道题我们考虑先看普通的 dp 怎么弄。

因为是按 $x$ 坐标依次连边，那我们先把点按 $x$ 坐标从小到大排序。那如果你在这里选一个集合，那在这里相连的就要连边。

那我们设 $f_{i,j,k}$ 为前 $i$ 个点在一定选 $i$ 号点中选到形成了 $j$ 段，然后最后一段的状态时 $k$。（$k$ 只有上升 $0$ 和下降 $1$ 两个值）

很容易想到转移方程是先分上升下降，然后要么跟原来最后一段状态一样，要么不一样。

我们先以变成上升，就是转移后 $k=0$ 的情况。

那如果不变，那就是段数不变，第一维要枚举 $1$ 到 $i-1$，$k$ 还是 $0$。 那如果改变，那就是段数增加了，原来的就要 $-1$，第一维还是枚举 $1\sim i-1$，那原来的 $k$ 就变成了 $1$。

那变成下降，也是同一个道理。

但是第一维就不是枚举 $1\sim i-1$，而是 $i+1\sim 100000$，因为你是从高变低。

至于初始化，就是 $f_{i,0,0}=f_{i,0,1}=1$。

但是你这样枚举会超时。

那我们考虑用一些数据结构优化它。 这个要求区间和，还有单点更新值，很容易就想到用树状数组。 那枚举 $1\sim i-1$ 就是直接查询 $i-1$ 的位置，$i+1\sim 100000$，就用查询 $100000$ 得出的值减去查询 $i$ 的得出的值。（就是前缀和的思想）

然后基本上就可以了，记得取模。

代码

#include
   
    #include
    
     #define mo 100007#define ll long longusing namespace std;struct node {   	int x, y;}zb[100001];int n, k;ll f[50001][11][2], tree[100001][11][2], re, ans;bool cmp(node X, node Y) {   	return X.x < Y.x;}void add(int now, int j, int k, ll add_num) {   //树状数组操作	for (int i = now; i <= 100000; i += i & (-i))		tree[i][j][k] = (tree[i][j][k] + add_num) % mo;}ll get(int now, int j, int k) {   	re = 0;	for (int i = now; i; i -= i & (-i))		re = (re + tree[i][j][k]) % mo;	return re;}int main() {   	scanf("%d %d", &n, &k);		for (int i = 1; i <= n; i++) {   		scanf("%d %d", &zb[i].x, &zb[i].y);	}		sort(zb + 1, zb + n + 1, cmp);//按 x 坐标排序		f[0][0][0] = 1;	f[0][0][1] = 1;	for (int i = 1; i <= n; i++) {   		f[i][0][0] = 1;		f[i][0][1] = 1;				add(zb[i].y, 0, 0, 1);		add(zb[i].y, 0, 1, 1);//初始化				for (int j = 1; j <= k; j++) {   			f[i][j][0] = (get(zb[i].y - 1, j, 0) + get(zb[i].y - 1, j - 1, 1)) % mo;			//可以是跟前面一样上升，也可以变换，成为新的一段			f[i][j][1] = ((get(100000, j, 1) - get(zb[i].y, j, 1) + get(100000, j - 1, 0) - get(zb[i].y, j - 1, 0)) % mo + mo) % mo;			//同理，可以跟前面一样下降，也可以变换，由原来的上升变成下降			//不过因为你是要下降，那你就要用全部减去上升的，才可以得到下降的			//树状数组搞的是上升的，那如果你找 100000，就是最大值的话，就所有都找了一遍，就是全部的了			//或者说这就是前缀和的思想						add(zb[i].y, j, 0, f[i][j][0]);			add(zb[i].y, j, 1, f[i][j][1]);			//放进树状数组里面		}				ans = (ans + f[i][k][0]) % mo;//统计答案		ans = (ans + f[i][k][1]) % mo;	}		printf("%lld", ans);		return 0;}