题解 P4066 【[SHOI2003]吃豆豆】

· · 题解

第一篇DP题解——

题意：

两个peachman吃peach，你可以决定两个peachman开始的位置，peachman走到peach的地方就会吃掉它，peachman只会向左或向上走，路线不可相交，问最多能吃多少peach。

暴力

其实也是个dp（记忆化搜索？），但思维难度明显少了很多。 很明显我们可以开一个四维数组表示第一个peachman和第二个peachman的位置。然后照传纸条跑就行了。

注意到题目上说路径不可以相交。

其实没有必要去管它。路径如果相交的话，换一下peachman就行了。

正解

拓扑排序+dp

因为一个点只能从它的右下角转移过来，所以我们可以将其看做一个DAG，然后拓排。

我们dp的顺序就是这个图的拓扑序。

Dp的连边不像网络流那么复杂，好像直接暴力连也能过，但很容易超时。

优化的方法是假如i，j连边，如果有一条边（i，k），满足x[j]<=x[k]&&y[j]<=y[k]，那么（i，k）就没有存在的必要了。

Dp方程很有意思，我们用f[i][j]表示a吃到了i点，b吃到了j点的最大值，转移的时候转移拓扑序小的那一维，并保证f[i][j]中，要么i的拓扑序始终大于j，要么j始终大于i。 同时，我们需要一个超级原点和终点来连上所有的点，最终的答案就是dp[超级终点][超级终点]-1。

inline void dp(int x,int y)//x,y是在主函数里枚举的x:超级原点-->终点   y:i-->终点
{
    int i,a,b;
    for(i=head[x];i;i=way[i].next)
    {
        a=way[i].to,b=y;
        if(id[a]>id[y]) swap(a,b);//注意这里
        if(a!=b) f[a][b]=max(f[a][b],f[x][y]+1);
        else f[a][b]=max(f[a][b],f[x][y]);
    }
}

为什么要减一呢？

我们注意一下dp方程，在统计的过程中，我们其实并不会将超级原点统计下来，但会加上一个超级终点的peach。减掉就好了。

为什么j要从i开始枚举呢？

因为这里转移的是i的出边，而不是i。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+7,M=2005;

struct node { int x,y; }g[N];
struct edge { int to,next; }way[N*300];int tot,head[N];
int n,cnt,ed,rd[N],id[N],ID[N],q[N*2];
int f[M][M];

inline void add(int x,int y)
{
    way[++tot].to=y;
    way[tot].next=head[x];
    head[x]=tot;
}

inline void tsort()
{
    int i,h=0,t=1,x;
    q[1]=0;
    while(h!=t)
    {
        x=q[++h];
        id[x]=++cnt;
        ID[cnt]=x;
        for(i=head[x];i;i=way[i].next)
        {
            if(--rd[way[i].to]==0)
            {
                q[++t]=way[i].to;
            }
        }
    }
}

inline void dp(int x,int y)
{
    int i,a,b;
    for(i=head[x];i;i=way[i].next)
    {
        a=way[i].to,b=y;
        if(id[a]>id[y]) swap(a,b);
        if(a!=b) f[a][b]=max(f[a][b],f[x][y]+1);
        else f[a][b]=max(f[a][b],f[x][y]);
    }
}

bool cmp(node x,node y)
{
    if(x.x!=y.x) return x.x<y.x;
    return x.y<y.y;
}

int main()
{
    int i,j,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d%d",&g[i].x,&g[i].y);
    sort(g+1,g+1+n,cmp);
    for(i=1;i<=n;i++)
    {
        t=1e9;
        for(j=i+1;j<=n;j++)
        {
            if(g[i].y<=g[j].y&&g[j].y<t)
            {
                t=g[j].y;
                rd[j]++;
                add(i,j);
            }
        }
    }
    ed=n+1;
    for(i=1;i<=n;i++)
    {
        add(0,i);  rd[i]++;
        add(i,ed); rd[ed]++;
    }
    tsort();
    for(i=1;i<=cnt;i++)
    {
        for(j=i;j<=cnt;j++)
        {
            dp(ID[i],ID[j]);
        }
    }
    printf("%d",f[ed][ed]-1);
    return 0;
}