题解 P2782 【友好城市】

Harker233333333 · 2017-07-04 11:57:41 · 题解

/*本题是简单的DP题

什么是不能交叉？当i>j且i友>j友时不交叉(可以自己划一下)

为了更加简单化，我们将一岸的城市按从小到大排序，这样只要求另一岸的无序数列的最长不下降数列了

首先我们用结构体和sort函数排序，而后再用DP模板即可*/

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
    int nor;
    int sou;
}city[50001];
int comp(node x,node y)
{
    if(x.sou<y.sou) return 1;
    else return 0;
}
int main()
{
    int ans=0;//答案 
    int i,j,Max=-1,map;//map:记录最大递增数列的初始位置 Max:找到最大递增数列
    int n,a[50001],b[50001];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    cin>>city[i].sou>>city[i].nor;
    sort(city+1,city+n+1,comp);//经过排序后可将问题转化为求最大递增数列的问题 
    fill(a+1,a+n+1,1);//开始时初始化所有的数列长度为1，即只包含其本身 
    memset(b,0,n);
    for(i=n-1;i>=1;i--)//阶段枚举
    for(j=i+1;j<=n;j++)//状态枚举 
    {
        if(city[j].nor>city[i].nor&&(a[j]+1)>a[i]) 
        {a[i]=a[j]+1;b[i]=j;}//决策_a:i~n最大递增数列  b:记录产生的路径 ——a[b[i]]->a[i] 
    }
    for(i=1;i<=n;i++)
    if(a[i]>Max){Max=a[i];map=i;}//找到最大递增数列
    while(map!=0)//循环查找数列长度
    {
        ans++;
        map=b[map];
    }
    cout<<ans;
    return 0;
}