HDOJ(HDU).1025 Constructing Roads In JGShining’s Kingdom (DP)

点我挑战题目

题目分析

题目大意就是给出两两配对的poor city和rich city，求解最多能修几条不相交的路。此题可以转化为LIS问题。转化过程如下：

数据中有2列，为方便表述，暂且叫做第一列和第二列。

1.若第一列是是递增的（给出的2个样例都是递增的），那么要想尽可能多的做连线，则那么就需要找出第二列中最长的递增子序列，若出现非递增的序列，那么连线后一定会相交。

2.若第一列不是递增的，排序后按照1分析即可。

综上所述，题目便转换成LIS问题。

LIS有2种写法，一种是o(n²)的写法，一种是o(nlogn)的写法。题目中给出n<=500,500.采用o(n²）必定超时，最佳策略是o(nlogn)。

推荐一篇介绍这种写法的博文 最长上升子序列nlogn算法。通俗易懂，在此就不赘述如何设计此算法了。

代码总览

/*

    Title:HDOJ.1025

    Author:pengwill

    Date:2017-2-15

*/

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define nmax 500005

using namespace std;

int a[nmax],dp[nmax];

int BS(int dt[],int t[],int left, int right,int i)

{

    int mid;

    while(left<right){

        mid = (left+right)/2;

        if(dt[mid]>=t[i]) right = mid;

        else left = mid+1;

    }

    return left;

}

int main()

{

//    freopen("in.txt","r",stdin);

    int n,t = 0;

    while(scanf("%d",&n) != EOF){

        printf("Case %d:\n",++t);

        int x,y;

        for(int i = 1;i<=n; ++i){scanf("%d%d",&x,&y);a[x] = y;}

        dp[1] = a[1];

        int len=1;

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

//            int m = 0;

//            for(int j = 1; j<i ;++j ){

//                if(a[i]>a[j] && dpa[j]>m)

//                    m = dpa[j];

//            }

//            dpa[i] = m+1;

//        }

        for(int i = 2; i<=n;++i){

            if(a[i]>dp[len]) dp[++len] = a[i];

            else{

                int pos = BS(dp,a,1,len,i);

                dp[pos] = a[i];

            }

        }

        if(len == 1) printf("My king, at most 1 road can be built.\n\n");

        else printf("My king, at most %d roads can be built.\n\n",len);

    }

    return 0;

}