求最长递增子序列~ - C语言论坛

第 11 楼

得分:0

2楼代码输入
10
100 150 200 300
201 202 203 204
9 8

的时候输出结果为5
期望结果应该是7
PS:8楼也是~
2018-3-18 22:25更

[此贴子已经被作者于2018-3-18 22:27编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 12 楼

得分:30

回复楼主九转星河

最近挺累的。回来也没时间写。找了个二分查找法。我去南阳理工OJ测试了一下。AC了。那题原本是N<=100000的序列长度，这里是50000的序列长度
不知道你这是哪里的OJ题。所以我改了一下数组长度。去掉了多组测试数据。其它均未改变。你试试看。
#include <stdio.h>
//#include <stdlib.h>

int LIS(int *array, int n);
int BiSearch(int *b, int len, int w);
int p[50009];
int B[50009];
int len;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &p[i]);
    }
    len = 0;
    printf("%d\n", LIS(p, n));

    return 0;
}

int LIS(int *array, int n)
{
    len = 1;
    B[0] = array[0];
    int i, pos = 0;

    for (i = 1; i<n; ++i)
    {
        if (array[i] > B[len - 1]) //如果大于B中最大的元素，则直接插入到B数组末尾
        {
            B[len] = array[i];
            ++len;
        }
        else
        {
            pos = BiSearch(B, len, array[i]); //二分查找需要插入的位置
            B[pos] = array[i];
        }
    }

    return len;
}

//修改的二分查找算法，返回数组元素需要插入的位置。
int BiSearch(int *b, int len, int w)
{
    int left = 0, right = len - 1;
    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (b[mid] > w)
            right = mid - 1;
        else if (b[mid] < w)
            left = mid + 1;
        else    //找到了该元素，则直接返回
            return mid;
    }
    return left;//数组b中不存在该元素，则返回该元素应该插入的位置
}

普通人之所以普通，是因为他们普遍有一个通病，那就是认为自己永远普通。
千夫所指，我亦坚持。就算被所有人误解，我也照样守护这一切。
我们总是觉得，这些灵魂的表情，傲慢自大，目中无人，其实，真正目中无人的是我们。它们傲慢的不过是表情，而我们傲慢的却是行为！
记得，是为了忘记！
只要想着有那么一天，我就能忍受现在的每一天！
灾难并不可怕，可怕的是心中没有了希望。
你以为我在天堂，其实我正在路上。
当你觉得自己走不到终点的时候，请不要放弃。或许你的对手也是这种感觉。

第 13 楼

得分:0

回复 12楼 lanke711

学习了

这个方法的确挺巧妙的~应该可以了

~

然后发现了原来是用了路径覆盖思想,的确比我那个求连通分量要简单很多,当然我那个方法理论上可以输出最长路径的~
当然了,能AC就可以了

[此贴子已经被作者于2018-3-19 08:04编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 14 楼

得分:30

动态规划的题

程序代码：

#include <stdio.h>
const int N = 50000;

int Bin(int key, int* d, int low, int high)
{
    while(low<=high)
    {
        int mid = (low+high)>>1;
        if(key>d[mid] && key<=d[mid+1])
            return mid;
        else if(key>d[mid])
            low = mid+1;
        else
            high = mid-1;
    }
    return 0;
}

int LIS(int* a, int n, int* d)
{
    int i,j;
    d[1] = a[1];
    int len = 1;
    for(i = 2; i <= n; i++)
    {
        if(d[len]<a[i])
            j = ++len;
        else
            j = Bin(a[i],d,1,len) + 1;//二分法查找
        d[j] = a[i];
    }
    return len;
}

int main()
{
    int a[N];
    int d[N];
    int t;
    int p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&p);
        for(int i = 1; i <= p; i++)
            scanf("%d",&a[i]);
        printf("%d\n",LIS(a,p,d));
    }
    return 0;
}

腾空类星陨，遥望若花生。

第 15 楼

得分:25

#include<stdio.h>

int LIS(int arr[1000], int n)
{
    int dp[100];
    for(int i=1; i<=n; ++i)
        dp[i] = 0;
    int ans;
    dp[1] = 1;
    for(int i=2; i<=n; ++i)
    {
        ans = dp[i];
        for(int j=1; j<i; ++j)
        {
            if(arr[i]>arr[j] && dp[j]>ans)
                ans = dp[j];
        }
        dp[i] = ans+1;
        //printf("dp[%d]=%d ",i,dp[i]);
    }
    ans = 0;
    for(int i=1; i<=n; ++i)
    {
        if(dp[i] > ans)
            ans = dp[i];
    }
    return ans;
}

int main()
  {
      int i,j,n,max,min,num=0;
      int count[100]={0};
      int a[100];
      scanf("%d",&n);
      for(i=1;i<=n;++i)
          scanf("%d",&a[i]);
      printf("\n%d",LIS(a,n));
      return 0;
  }

第 16 楼

得分:0

回复 15楼 ehszt

这个是常规算法,容易理解~
就是用常规算法进行查找来获取位置 ~
但如果要卡效率的话这算法复杂度o(n^2)有可能超时哦

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 17 楼

得分:0

重写了sbeach函数,实现形式参考了标准库函数bsearch,实现主体参考了12楼的代码(特别拜谢

),当然个人感觉14楼的二分法查找下标从1开始适用范围比较有局限性
这个函数感觉这个对于查找最近插入点有一定帮助的,可以参考一下

程序代码：

size_t BsearchReIndex( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) )
{
   size_t low=0;
   size_t height=num-1;
   
   while (low<=height&&height!=-1)
   {
       const size_t mid=low+(height-low>>1);
       
     const int comp=compartor(key,( const char* )base+mid*size);
       
    if (comp<0)
        height=mid-1;
    else if (comp>0)
        low=mid+1;
    else
        return mid;
   }

   return low;
}

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 18 楼

得分:0

写了个输出路径的,感觉有点绕,看看就行了

程序代码：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>

#define FREE( p )    \
    do    \
    {    \
        free(p);    \
        p=NULL;    \
    }while (0)

typedef struct Data
{
    int data;    //保存数据
    size_t mark;    //上一个数据下标
    
}Data,*P_Data;

size_t _bsearch( const void*,const void*,size_t,size_t ,int (*)( const void*,const void* ));

int comp(const void* ,const void* );

void malFun( void**,size_t );
void input( const P_Data*,size_t );

void printData( const Data[],size_t );

unsigned fun( Data[],size_t );

int main( void )
{
    P_Data data=NULL;
    
    size_t len=0;
    
    if ( !scanf("%u",( unsigned* )&len))
        exit(EXIT_FAILURE);

    input(&data,len);

    printData(data,fun(data,len));
    
    FREE(data);

    return 0;
}

int comp(const void* p,const void* q)
{
    const int _p=*( const int* )p;
    const P_Data _q=( const P_Data )q;

    if (_p>_q->data)
        return 1;
    
    if (_p<_q->data)
        return -1;
        
    return 0;
}

size_t _bsearch( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) )
{
   size_t low=0;
   size_t height=num-1;
   
   while (low<=height&&height!=-1)
   {
       const size_t mid=low+(height-low>>1);
       
     const int comp=compartor(key,( const char* )base+mid*size);

    if (comp<0)
        height=mid-1;
    else if (comp>0)
        low=mid+1;
    else
        return mid;
   }

   return low;
}

void malFun( void** data,size_t size )
{
    assert(data);
    
    *data=malloc(size);
    
    assert(*data);
    
    memset(*data,0,size);
}

void input( const P_Data* data,size_t len)
{
    const size_t size=len*sizeof (Data);
    size_t i;
    
    if (!len)
        exit(EXIT_FAILURE);
    
    malFun(( void** )data,size);
    
    for (i=0;i!=len;++i)
        if (!scanf("%d",&(*data)[i].data))
            exit(EXIT_FAILURE);
        else
            (*data)[i].mark=i;
            
       
}

unsigned fun( Data data[],size_t len )
{
    P_Data road=NULL;

    const size_t dataSize=len*sizeof (Data);
    const size_t roadSize=len*sizeof (Data);
    
    size_t pos=0;
    
    size_t i;
    size_t j=1;
    
    malFun(( void** )&road,roadSize);
    
    road[0].data=data[0].data;
    road[0].mark=0;

    for (i=0;i!=len;++i)
        data[i].mark=-1;
    
    for (i=1;i<len;++i)
    {
        if (data[i].data>road[j-1].data)
            pos=j++;
        else
            pos=_bsearch(&data[i].data,road,j,sizeof (Data),comp);

       if (pos)
            data[i].mark=road[pos-1].mark;
        
        road[pos].data=data[i].data;
        road[pos].mark=i;

    }
    
    pos=road[j-1].mark;
   
   FREE(road);

    return pos;
}

void printData( const Data data[],size_t mark )
{
    int* road=NULL;
    
    size_t step;
    size_t t_step;
    
    size_t t_mark=mark;
    
    for (step=0;mark!=-1;++step)
        mark=data[mark].mark;

    malFun(( void** )&road,step*sizeof (int));
    
    for (t_step=step-1,mark=t_mark;mark!=-1;--t_step)
    {
        road[t_step]=data[mark].data;
        mark=data[mark].mark;
    }

     printf("\n最长子序列长度为%u,具体路径为:\n",( unsigned )step);
    while (++t_step!=step)
        printf("%-8d",road[t_step]);
    
    puts("");
    FREE(road);
}

[此贴子已经被作者于2018-3-20 08:28编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 19 楼

得分:10

#include<stdio.h>
int dp[100];
int LIS(int arr[1000], int n)
{

    for(int i=1; i<=n; ++i)
        dp[i] = 0;
    int ans;
    dp[1] = 1;
    for(int i=2; i<=n; ++i)
    {
        ans = dp[i];
        for(int j=1; j<i; ++j)
        {
            if(arr[i]>arr[j] && dp[j]>ans)
                ans = dp[j];
        }
        dp[i] = ans+1;
        //printf("dp[%d]=%d ",i,dp[i]);    //每个数都有一个dp值
    }
    ans = 0;
    for(int i=1; i<=n; ++i)
    {
        if(dp[i] > ans)
            ans = dp[i];
    }
    return ans;
}

void footprint(int m,int n,int a[]) //打印路径
{
    int b[m+1];
    int c=m;
    for(int i=n;i>0;i--)
    {
        if(dp[i]==c)
        {
            b[c]=a[i];
            c--;
        }
    }
    printf("\n");
    for(int i=1;i<=m;i++)
    {
        printf("%d ",b[i]);
    }
}

int main()
  {
      int i,j,n,max,min,num=0,m;
      int count[100]={0};
      int a[100];
      scanf("%d",&n);
      for(i=1;i<=n;++i)
          scanf("%d",&a[i]);
      printf("\n%d",m=LIS(a,n));
      footprint(m,n,a);
      return 0;
  }

[此贴子已经被作者于2018-3-20 10:47编辑过]

第 20 楼

得分:0

回复 19楼 ehszt

赶紧吃个瓜来缓冲一下

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]