题解 P2782 【友好城市】

StyWang · 2017-12-12 21:25:17 · 题解

分析

要求最优解，所以考虑使用dp。

如果要使用dp，首先一定要对数据进行排序，再尝试写出状态转移方程。

题目要求任意两条航路不相交，由此想到按照某一个岸边的坐标进行排序，因为这样排序，在判断航路是否相交时非常简便。

按照岸边坐标排序后，从第1条到第n条航路互不相交的充要条件是这些航路的另一个岸边的坐标为单调不减数列。

分析到这里，做法很清晰了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define MAX 5005
using namespace std;

struct stu
{
    int start;        //第一个岸边坐标
    int end;        //第二个岸边坐标
};
struct stu river[MAX];
int dp[MAX] = {0};
int N;
int ans = 1;
bool cmp_start(struct stu x, struct stu y);
bool check(int i, int j);

int main()
{
    int i, j;
    scanf("%d", &N);
    for(i = 1; i <= N; i++)
    {
        scanf("%d%d", &river[i].start, &river[i].end);
    }

    for(i = 0; i <= N; i++)
    {
        dp[i] = 1;//注意初始化边界条件，否则会WA
    }

    sort(river + 1, river + 1 + N, cmp_start);
    //按照start的值进行排序

    for(i = 1; i <= N; i++)
    {
        for(j = i + 1; j <= N; j++)
        {
            if(river[i].end <= river[j].end)
            {
                dp[j] = max(dp[j], dp[i] + 1);//和最长不下降子序列的dp一样
            }
        }
        ans = max(ans, dp[i]);
    }

    printf("%d", ans);
    return 0;

}


bool cmp_start(struct stu x, struct stu y)
{
    return x.start < y.start;
}