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;
}