首页 > 代码库 > hdu1025 最大递增子序列

hdu1025 最大递增子序列

2024-08-04 04:15:42   220人阅读

把题意转换一下就是最大递增子序列问题   不过就是数的排列不是按输入顺序

500000果断用n*logN的时间复杂度

这个算法是把每个数一个个往里面插入  然后一步步更新len（当前最大子序列）  最后得出全局的最大子序列
num【i】表示数i出现的位置  dis【k】表示子序列长度为k的出现的最小的位置（比如x=dis【k】表示最先出现子序列为k的位置为x）
注意for循环跑到i表示以num【i】结尾的最大子序列

现在就出现两种情况
1》dis【len】<num【i】 这个好说  直接令len++   然后令dis【len】=num【i】；
2》dis【len】》num【i】 然后用二分查找到最小的j是dis【j】>num【i】；令dis【j】=num【i】 注意讨论没有的情况


下面是详细代码
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int dis[500010],num[500010];
int main()
{
    int n,i,j,a,b,d=1;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            num[a]=b;
        }
        int len=1;
        int L,R;
        dis[1]=num[1];
        for(i=2;i<=n;i++)
        {
            if(dis[len]<num[i])
            {
                len++;
                dis[len]=num[i];
            }                    
            else if(dis[len]>num[i])
            {
                L=1;
                R=len;
                int flash=0;
                while(L<=R)
                {
                    int mid=(L+R)/2;
                    if(dis[mid]<num[i]) L=mid+1;
                    else if(dis[mid]>num[i])R=mid-1;
                    else {flash==1;break;}
                }
                if(!flash)dis[L]=num[i];
            }    
        }
        printf("Case %d:\n",d++);
        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");
        printf("\n");
    }
    return 0;
}

hdu1025 最大递增子序列


联系
我们