ny214 单调递增子序列(二) 动态规划

单调递增子序列(二)

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述

给定一整型数列{a₁,a₂...,a_n}（0<n<=100000），找出单调递增最长子序列，并求出其长度。

如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。

输入

有多组测试数据（<=7）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的下一行里有n个整数，表示数列中的所有元素.每个整形数中间用空格间隔开（0<n<=100000）。
数据以EOF结束。
输入数据保证合法（全为int型整数）！

输出

对于每组测试数据输出整形数列的最长递增子序列的长度，每个输出占一行。

样例输入

7

1 9 10 5 11 2 13

2

2 -1

样例输出

5

1
常规方法，会超时的，AC代码一：

#include<stdio.h>

#include<string.h>

int main()

{

    int b[],a[];

    int i,j,n,t,max;

    while(scanf("%d",&t)!=EOF)

    {    max=;

        memset(b,,sizeof(b));

        for(i=;i<t;i++)

            scanf("%d",&a[i]);

        b[] = a[];

        for(i = , j = ; i < t; i++)

        {

            if(a[i]> b[j-])//判断如果出现后面的有大于前面的数就保存起来；

                b[j++] = a[i];//保存的同时，j的值也在不断的增大，当保存到最后，j的值就是最后的最大长度了；

            else{

                for(int k = ; k < j; k++)

                {

                    if(a[i] < b[k]){

                        b[k] = a[i];

                        break;

                    }

                }

            }

        }

        printf("%d\n",j);

    }

    return ;

}

AC代码二：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 int dp[];

 int main()

 {

     int i,a,t,k,j,n,mm;

     while(scanf("%d",&n)!=EOF)

     {  k=;memset(dp,,sizeof(dp));mm=;

            cin>>dp[];

         for(i=;i<n;i++)

         {

             scanf("%d",&a);

             if(a<dp[])

                 dp[]=a;

               else if(a>dp[k-])

                      dp[k++]=a;

               else

               {

                  for(j=;j<k;j++)

                     {

                       if(a<dp[j] && a>dp[j-])

                         {dp[j]=a;break;}

                       else  if(a<dp[j])

                             break;

                     }

                }

         }

         cout<<k<<endl;

     }

     return ;

 }

超时的代码：

#include<stdio.h>

#include<string.h>

//int b[100010]={0};

int main()

{

    int a[],b[];

    int i,j,n,t,max;

    while(scanf("%d",&t)!=EOF)

    {max=;

        memset(b,,sizeof(b));

        scanf("%d",&a[]);

        for(i=;i<t;i++)

        {

            scanf("%d",&a[i]);

            for(j=;j<i;j++)

                if(a[i]>a[j] && b[j]+>b[i])

                b[i]++;

            //    printf("%d ",b[i]);

                if(b[i]>max)

                    max=b[i];

        }

        /*for(i=0;i<t;i++)

        {if(b[i]>max)

        max=b[i];

        }*/

        printf("%d\n",max+);

    }

    return ;

}

巴特西

ny214 单调递增子序列(二) 动态规划

单调递增子序列(二)

最新文章

热门文章