hdu 1025 dp+二分模板

野性酷女 2022-08-20 07:18 169阅读 0赞

题意：

在一条河的两边各有n个位置，在这些位置之间建桥，要求所有桥之间不能交叉。现在告诉你所有可以建桥的位置，例如2,4，就是说河左边的位置2可以与河右边的位置4之间建桥，现在要求满足要求的情况下最多可以建桥的个数。

分析：

想了好久发现是一个最长上升子序列问题，当时n比较大，所以一般的dp算法不能解决这个问题，所以我们换一种专门解决这个问题的特殊解法，就是用dp+二分，但是只能解决序列的长度而不能求出序列。

下面的解释摘自Lce\_Crazy的博客。

假定存在一个序列d\[1...9\]=2 1 5 3 6 4 8 9 7，可以看出LIS长度为5。现在开始一步一步的找出来最终的结果。

定义序列B，令i=1...9来逐个考察。此外用变量len来记录现在最长算到了多少了。

首先，把d\[1\]放到B里，即B\[1\]=d\[1\]，就是说长度为1的LIS的最小末尾是2，这时len=1，然后把d\[2\]有序的放到B里，令B\[1\]=1（d\[2\]），就是说长度为1的LIS最小末尾是1，d\[1\]=2已经没有用了，这是len=1不变。接着d\[3\]=5,5>1，所以令B\[1+1\]=d\[3\]=5，就是说长度为2的LIS的最小末尾是5，此时B\[1...2\]=1,5，len=2。

再来，d\[4\]=3，它正好在1和5之间，当然放在1的位置上不合适，因为1<3，因此长度为2的最小末尾应该是3，淘汰掉5，这时候B\[1...2\]=1,3，len=2，继续d\[5\]=6，它在3后边，所以B\[3\]=4，B\[1...3\]=1,3,6，len=3。

第6个，d\[6\]=4，它加在3和6之间，所以我们把6换掉，这样B\[1...3\]=1,3,4，len=3。

第7个，d\[7\]=8，8>4，所以B\[4\]=8，B\[1...4\]=1,3,4,8，len=4。

第8个，d\[8\]=9，B\[1...5\]=1,3,4,8,9，len=5。

最后一个，d\[9\]=7，所以B\[1...5\]=1,3,4,7,9，len=5。

注意这里的B并不是LIS，而是对应长度的LIS的最小末尾。

现在可以发现B插入数据是有序的，而且进行替换而不需要移动，也就是说可以使用二分查找，时间复杂度就降下来了。

//之前见过的建桥问题建桥问题
    //求最长上升子序列的长度，n比较大，不能用普通的dp，会超时
    //只求长度，可以用dp+二分
    
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int  num[50001];
    int  ans[50001];
    int main()
    {
        int n,k=1;
        int len,low,heigh,mid;
        int tmp1,tmp2;
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d %d",&tmp1,&tmp2);
                num[tmp1]=tmp2;
            }
            memset(ans,0,sizeof(ans));
            ans[1]=num[1];
            len=1;
            for(int i=2;i<=n;i++)
            {
                low=1;
                heigh=len;
                while(low<=heigh)
                {
                    mid=(low+heigh)/2;
                    if(ans[mid]<num[i])
                        low=mid+1;
                    else
                        heigh=mid-1;
                }
                ans[low]=num[i];
                if(low>len)
                    len++;
            }
            printf("Case %d:\n",k);
            if(len==1)
                printf("My king, at most 1 road can be built.");
            else
                printf("My king, at most %d roads can be built.",len);
    
            printf("\n\n");
            k++;
        }
        return 0;
    }