hdu 1025 Constructing Roads In JGShining's Kingdom (LIS)

题意：国王修路问题。道路不能交叉，问最多能修多少条路。

分析：

把对应的匹配位置记下来，然后找位置坐标的LIS。跟那题把LCS

转化为LIS一样的思路

uva 10635 Prince and Princess (将LCS 转化为 LIS)

只不过是那题找的是同一个数在另一序列出现的位置，这题找的是和当前数匹配的数在

另一序列中的位置。

二分可以把o(n*n)的LIS算法优化到o(nlogn）

就是不断地更新dp数组里的数，不断的记录下能够得到的最大值。

这题还要注意一条路是road，多条是roads。每一组后空一行。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int dp[500005],cc[500005];
int n;

int LIS()
{
    int low,high,len,mid;
    dp[1]=cc[1],len=1;
    for(int i=2;i<=n;i++)
    {
        low=1;high=len;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(cc[i]<dp[mid])
                high=mid-1;
            else
                low=mid+1;
        }
        dp[low]=cc[i];
        if(low>len)
            len=low;
    }
    return len;
}

int main()
{
    int a,b,cas=1,ans;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            cc[a]=b;
        }
        ans=LIS();
        printf("Case %d:\n",cas++);
        if(ans==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",ans);
    }
    return 0;
}

hdu 1025 Constructing Roads In JGShining's Kingdom (LIS)

原文：http://blog.csdn.net/u012841845/article/details/18654921