题解 P2782 【友好城市】

dj114133643 · 2017-10-02 22:51:10 · 题解

大家都是求最长不下降子序列，

而我用的是正宗纯粹DP

F[I][J]表示只用北岸前I个，南岸前J个（可以不用），

最大连线数。

只需考虑北岸第I个是否使用即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct node
{
    int id;
    int zb;
}x[5005],y[5005];
int f[5005][5005];
bool cmp(node aa,node bb)
{
    return aa.zb<bb.zb;
}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i].zb,&y[i].zb);
        x[i].id=y[i].id=i;
    }
    sort(x+1,x+n+1,cmp);
    sort(y+1,y+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        for(j=1;y[j].id!=x[i].id;j++)
            f[i][j]=f[i-1][j];
        f[i][j]=f[i][j-1]+1;
        for(j=j+1;j<=n;j++)
            f[i][j]=max(f[i-1][j],f[i][j-1]);
    }
    printf("%d\n",f[n][n]);
    return 0;
}