题目链接

题解

将点排序

设\(f[i][j][0|1]\)表示以第\(i\)点结尾，有\(j\)段，最后一段上升或者下降的方案数

以上升为例

\[f[i][j][0] = \sum\limits_{k = 1}^{i - 1}\sum\limits_{y_k < y_i}f[k][j][0] + \sum\limits_{k = 1}^{i - 1}\sum\limits_{y_k < y_i}f[k][j - 1][1]
\]

\(bit\)优化成\(O(knlogn)\)

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define cls(s,v) memset(s,v,sizeof(s))

#define mp(a,b) make_pair<int,int>(a,b)

#define cp pair<int,int>

#define lbt(x) (x & -x)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f,P = 100007;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}

	return flag ? out : -out;

}

int f[maxn][12][2],N = 100000;

int S[2][2][maxn],n,x[maxn],y[maxn],id[maxn],K;

void add(int* s,int u,int v){while (u <= N) s[u] = (s[u] + v) % P,u += lbt(u);}

int query(int* s,int u){int re = 0; while (u) re = (re + s[u]) % P,u -= lbt(u); return re;}

int sum(int* s,int l,int r){return query(s,r) - query(s,l - 1);}

inline bool cmp(const int& a,const int& b){return x[a] < x[b];}

int main(){

	n = read(); K = read();

	REP(i,n) x[i] = read(),y[i] = read(),id[i] = i;

	sort(id + 1,id + 1 + n,cmp);

	REP(i,n) f[i][0][0] = f[i][0][1] = 1;

	for (int k = 1; k <= K; k++){

		cls(S,0);

		for (int i = 1; i <= n; i++){

			int u = id[i];

			f[u][k][0] = (sum(S[1][0],1,y[u]) + sum(S[0][1],1,y[u])) % P;

			f[u][k][1] = (sum(S[1][1],y[u],N) + sum(S[0][0],y[u],N)) % P;

			add(S[0][0],y[u],f[u][k - 1][0]);

			add(S[1][0],y[u],f[u][k][0]);

			add(S[0][1],y[u],f[u][k - 1][1]);

			add(S[1][1],y[u],f[u][k][1]);

		}

	}

	int ans = 0;

	for (int i = 1; i <= n; i++) ans = (ans + f[i][K][0] + f[i][K][1]) % P;

	printf("%d\n",(ans + P) % P);

	return 0;

}

巴特西

BZOJ3688 折线统计【dp + BIT】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ3688 折线统计 【dp + BIT】

题目链接

题解

最新文章

热门文章

BZOJ3688 折线统计【dp + BIT】