首页 > 代码库 > HDU 5141

HDU 5141

2024-08-06 13:57:11   220人阅读

这个题 LIS  +  并查集的思想 + 链式前向星 

要求找s(i,j)使i j 能有最长的LIS  。。。

做法是枚举每一个j 即终点  算 起点 的可能

无力吐槽了  bc 的时候写错了一个地方 导致TLE  后来幡然醒悟了  

改了就a了 

+++++++++++++++++++++++++++++++++++++++++++

不想说什么了 直接上代码

+++++++++++++++++++++++++++++++++++++++++++

#include <cstdio>#include <cmath>#include <algorithm>#include <iostream>#include <cstdlib>#include <string>#include <queue>#include <map>#include <stack>#include <cstring>#define CL(a,b) memset(a,b,sizeof(a))#define ll __int64#define TEST cout<<"TEST   ***"<<endl;#define INF 0x7ffffff0#define MOD 1000000007using namespace std;typedef struct node{    int p,next;}N;N no[100010];int head[100010],cv;int num[100010];int fa[100010];int pi[100010];int so[100010],ct;int n;void inithead(){    CL(head,-1);    cv=0;}void addnode(int s,int e){    no[cv].p=e;no[cv].next=head[s];head[s]=cv++;}void initfa(){    int i,j;    for(i=0;i<=100000;i++)fa[i]=i;}int finr(int x){    if(fa[x]==x)return x;    fa[x]=finr(fa[x]);    return fa[x];}void unio(int x,int y){    int rx=finr(x);    int ry=finr(y);    fa[rx]=ry;}int bin(int s,int e,int v){    int m=(s+e)/2;    if(so[m]>=v&&so[m-1]<v)return m;    if(so[m]>v)return bin(s,m,v);    return bin(m+1,e,v);}int main(){    while(scanf("%d",&n)!=EOF)    {        int i,j,a,p,v;        initfa();        inithead();        so[0]=-1;ct=0;        for(i=1;i<=n;i++)        {            scanf("%d",&a);            num[i]=a;            if(a>so[ct])            {                ct++;                so[ct]=a;                addnode(ct,i);                pi[i]=ct;            }            else            {                p=bin(0,ct,a);                so[p]=a;                addnode(p,i);                pi[i]=p;            }            if(pi[i]!=1)            {                p=head[pi[i]-1];                while(p!=-1)                {                    v=no[p].p;                    if(num[v]<a)                    {                        unio(i,v);                        break;                    }                    p=no[p].next;                }            }        }        ll rem=0,la=0,he;        i=n;        while(i>=1)        {            la++;            if(pi[i]==ct)            {                he=finr(i);                rem+=la*he;                la=0;            }            i--;        }        printf("%I64d\n",rem);    }    return 0;}

 

HDU 5141


联系
我们