学步园

这个是很久以前敲过的。。今天又用到LIS 的nlogn算法了。。于是回顾。但是自己的代码好半天没看懂。。看来写题解真的好重要啊。

最后看别人的看懂了。。。

这种算法用一个数组stack stack[i]表示目前为止 lis的长度为i的 最末尾的数字的最小值。 这个值应该尽可能小 这样后面的数字更可能插入到这个序列。

对原来的数组arr进行迭代 从 首先stack[1]=arr[i]；

然后从2 到 n 对于每个arr[i] 从stack中找到那个比它大的最小值。的下标 arr[i] 应该比这个下标的前一个大 但是比这个下标小 也就是说更新长度为index的lis的最末尾的值

考虑这样一个序列 9 个数 2 1 5 3 6 4 8 9 7 我们能看出 lis长度为5

首先stack[1]=arr[1]=2;

接着 i=2 比stack[1]小 所以 我们更新长度为1的lis的最末尾的值 stack[1]更新为1

接着 i=3 arr[3]=5 比1 大了 这样我们插入stack stack 为 1 5 

接着i=4 元素是3 我们找到 5 3比5小 所以更新 长度为2的 lis的末尾的值 变成 3 stack变成 1 3

接着i=5 6比3大 插入 stack变成1 3 6

接着i=6 4比6小 更新为 1 3 4

接着i=7 8比4大 插入后 len变成4 stack 是 1 3 4 8

接着i=8 9比8大 插入 len变成5 stack是 1 3 4 8 9

接着 i=9 7比8小 所以更新长度为4的lis的末尾值 stack为 1 3 4 7 9

注意最后这个stack 不是 lis 最后一步更新 其实也没用了 但是如果后面再有个 8 9的话  原来的9变成8 然后再加一个9 lis是6！

还有stack是有序的 所以每次找这个位置的时候二分就可以了 如果 最后一步arr[i]>stack[mid] 那么 low变成mid+1

否则的话 low 就是mid 这样 就保证 arr[i] 是更新了原来那个长度的最小末尾。

这个算法真太神了。。真不知道啥人想出来的。。。

记得第一次和疼 还有我现在媳妇儿一起参加市赛的时候 就有一个 lis 最后我们才懂 那个要求算法到nlogn。。 但是当时不会啊。

说起媳妇儿了。。我还想说一句话 ACM brings me so much、、、

不菜了 上代码。

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

const int maxn=500005;

int arr[maxn];
int stack[maxn];

int main()
{
    int n,i,j,a,b,ca=1;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;++i)
        {
            scanf("%d%d",&a,&b);
            arr[a]=b;
        }
        stack[1]=arr[1];
        int low,mid,high;
        int len=1;
        for(i=2;i<=n;++i)
        {
            low=1;high=len;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(arr[i]>stack[mid])
                low=mid+1;
                else
                high=mid-1;
            }
            stack[low]=arr[i];
            if(low>len)
            len++;
        }
        if(len>1)
            printf("Case %d:\nMy king, at most %d roads can be built.\n\n",ca,len);
        else
            printf("Case %d:\nMy king, at most %d road can be built.\n\n",ca,len);
        ca++;
    }
    return 0;
}