Description：

两个人可以向右或向上走，行走路线不能相交，在一些位置会得到收益，求最大收益。

$1\leqslant n\leqslant 2000$

Solution：

加了访问次数的传纸条，那就拆点，限制每个点流量为 $1$ 费用为 $1$ ，跑最大费用最大流，但是这样建的边数最大可能是 $O(n^2)$ 的，于是我们可以考虑减少边数，如果 $a$ 在 $b$ 的左下方， $b$ 在 $c$ 的左下方，我们可以看成是 $a$ 经过了 $b$ ，但是没有获取权值，也没有占用流量，因此对于每个点按横坐标从大到小枚举他左下方的点，那么这个点再左下方的点就不朝他连边了，并且每个点在拆点的两个点之间在连一条容量无穷费用为 $0$ 的边代表不经过他即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 4010

struct point

{

	int x,y;

}p[MAXN];

bool cmp_x(point a,point b){return a.x < b.x;}

int s,ss,t;

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt,f,c;

}e[10000000];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int f,int c)

{

	e[edgenum] = (edge){b,lin[a],f,c};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-c};lin[b] = edgenum++;

	return;

}

int pre[MAXN],rate[MAXN],d[MAXN];

bool inq[MAXN];

bool SPFA()

{

	memset(d,-1,sizeof(d));

	memset(rate,0,sizeof(rate));

	rate[s] = INF;

	queue<int> q;q.push(s);

	d[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] < d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return rate[t] != 0;

}

int flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t] * d[t];

}

int EK()

{

	int ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d",&p[i].x,&p[i].y);

	s = 2 * n + 1;ss = s + 1;t = ss + 1;

	add(s,ss,2,0);

	for(int i = 1;i <= n;++i)add(ss,i * 2 - 1,INF,0),add(i * 2,t,INF,0);

	for(int i = 1;i <= n;++i)add(i * 2 - 1,i * 2,1,1),add(i * 2 - 1,i * 2,INF,0);

	sort(p + 1,p + 1 + n,cmp_x);

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

	{

		int lastx = INF,lasty = 0;

		for(int j = n;j >= 1;--j)

		{

			if(i == j)continue;

			if(p[j].x > p[i].x)continue;

			if(p[j].y > lasty && p[j].y <= p[i].y)

			{

				add(j * 2,i * 2 - 1,INF,0);

				lasty = p[j].y;

			}

		}

	}

	cout << EK() << endl;

	return 0;

}