题意：两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。

---

暴力建图会被卡内存，可以按lis剖分建图...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;#define fir first#define sec secondconst int N = 5005, M = 1e6+5, mo = 1e9+7;inline int read() {    char c=getchar(); int x=0,f=1;    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}    return x*f;}int n, s, t, ss, tt;struct meow {    int x, y;    bool operator <(const meow &r) const {return x == r.x ? y < r.y : x < r.x;}} a[2005];struct edge {int v, ne, c, f, w;} e[M];int cnt = 1, h[N];inline void ins(int u, int v, int c, int w) { //printf("ins %d --> %d\n", u, v);    e[++cnt] = (edge) {v, h[u], c, 0, w};  h[u] = cnt;    e[++cnt] = (edge) {u, h[v], 0, 0, -w}; h[v] = cnt;}void build() {    s=0; ss=n+n+1; tt=n+n+2; t=n+n+3;    ins(s, ss, 2, 0); ins(tt, t, 2, 0);    static bool mark[N];    for(int i=1; i<=n; i++) {        ins(i, n+i, 1, 1); ins(i, n+i, 1, 0);        int high = 0;        for(int j=i-1; j>=1; j--)             if(a[j].y > high && a[j].y <= a[i].y) ins(j+n, i, 2, 0), high = a[j].y, mark[j] = 1;        if(!high) ins(ss, i, 2, 0);    }    for(int i=1; i<=n; i++) if(!mark[i]) ins(i+n, tt, 2, 0);}namespace flow {    int d[N], inq[N], q[N], head, tail;     pair
         
           pre[N]; inline void lop(int &x) {if(x == N) x = 1; else if(x == 0) x = N-1;} bool spfa() { head = tail = 1; //memset(d, -1, sizeof(d)); for(int i=s; i<=t; i++) d[i] = -1e9; memset(inq, 0, sizeof(inq)); d[s] = 0; q[tail++] = s; inq[s] = 1; pre[t].fir = -1; while(head != tail) { int u = q[head++]; inq[u] = 0; lop(head); for(int i=h[u]; i; i=e[i].ne) if(e[i].c > e[i].f) { int v = e[i].v; if(d[v] < d[u] + e[i].w) { d[v] = d[u] + e[i].w; pre[v] = make_pair(u, i); if(!inq[v]) { inq[v] = 1; //if(d[v] > d[q[head]]) head--, lop(head), q[head] = v; //else q[tail++] = v, lop(tail); q[tail++] = v; lop(tail); } } } } return pre[t].fir != -1; } int mcmf() { int flow = 0, cost = 0; while(spfa()) { int f = 1e9, x; for(int i=t; i != s; i = pre[i].fir) x = pre[i].sec, f = min(f, e[x].c - e[x].f); flow += f; cost += d[t] * f; for(int i=t; i != s; i = pre[i].fir) x = pre[i].sec, e[x].f += f, e[x^1].f -= f; } return cost; }}void print(meow &a) {printf("(%d, %d)\n", a.x, a.y);}int main() { freopen("in", "r", stdin); n = read(); for(int i=1; i<=n; i++) a[i].x = read(), a[i].y = read(); sort(a+1, a+n+1); //for(int i=1; i<=n; i++) print(a[i]); build(); int ans = flow::mcmf(); printf("%d\n", ans);}