Eva

Time Limit: 10 Sec  Memory Limit: 64 MB
Description

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

第一行为一个整数N，表示豆豆的数目。 接下来 N 行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。 

仅有一行包含一个整数，即两个PACMAN加起来最多能吃掉的豆豆数量

8

8 1

1 5

5 7

2 2

7 8

4 6

3 3

6 4

7

 

N < = 2000

/**************************************************************

    Problem: 1930

    User: ictsing

    Language: C++

    Result: Accepted

    Time:244 ms

    Memory:42388 kb

****************************************************************/

 

//BZOJ1930 [Shoi2003]pacman 吃豆豆

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

const int inf = 1e9;

int s=0,t;

int s1,t1;

const int mt = 4000+5;

int fr[2100000],to[2100000],nxt[2100000],cap[2100000],cost[2100000],adj[mt],cur[mt];

bool inq[mt];

int dis[mt],lev[mt];

int ecnt=1;

struct node

{

    int x,y;

}a[mt>>1];

bool operator < (node a,node b)

{

    if(a.x==b.x) return a.y<b.y;

    return a.x<b.x;

}

int ans=0;

queue<int>q;

int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v,int cc,int ccc)

{

    ecnt++,fr[ecnt]=u,to[ecnt]=v,nxt[ecnt]=adj[u],cap[ecnt]=cc,cost[ecnt]=ccc,adj[u]=ecnt;

    ecnt++,fr[ecnt]=v,to[ecnt]=u,nxt[ecnt]=adj[v],cap[ecnt]=0,cost[ecnt]=-ccc,adj[v]=ecnt;

}

bool spfa()

{

    while(!q.empty()) q.pop();

    for(int i=s;i<=t;i++) dis[i]=inf,inq[i]=0;

    q.push(s),dis[s]=0,inq[s]=1;

    while(!q.empty())

    {

        int u=q.front();q.pop();inq[u]=0;

        for(int i=adj[u];i;i=nxt[i])

        {

            int v=to[i];

            if(dis[v]>dis[u]+cost[i]&&cap[i])

            {

                dis[v]=dis[u]+cost[i];cur[v]=i;

                if(!inq[v]) inq[v]=1,q.push(v); 

            }

        }

    }

    return dis[t]!=inf;

}

void mcf()

{

    while(spfa())

    {

        int tmp=inf;

        for(int i=cur[t];i;i=cur[fr[i]]) tmp=min(tmp,cap[i]);

        ans+=dis[t]*tmp;

        for(int i=cur[t];i;i=cur[fr[i]]) cap[i]-=tmp,cap[i^1]+=tmp;

    } 

}

int main()

{

    int n=read();

    s1=n+n+1,t1=s1+1,s=0,t=t1+1;

    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++)

        adde(s1,i,1,0),

        adde(i,i+n,1,-1),

        adde(i,i+n,1,0),

        adde(i+n,t1,1,0);

    adde(s,s1,2,0);

    adde(t1,t,2,0);

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

    {

        int tmp=inf;

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

        {

            if(a[j].y<tmp&&a[j].y>=a[i].y)

                adde(i+n,j,2,0);

            if(a[j].y>=a[i].y)

                tmp=min(tmp,a[j].y);

        }

    }

    mcf();

    printf("%d\n",-ans);

    return 0;

}