NYOJ 79 & 17 & 214 单调最长子序列问题（DP）

先解释下什么叫子序列。若a序列删去其中若干个元素后与b序列完全相同，则称b是a的子序列。

我们假定存在一个单调序列{An}（以递增序列为例)，现在在其后面添加一个元素a(n+1)，有两种情况：

1.a(n+1)>a(n) 。此时，a(n+1)可以添加到An序列的尾部，形成一个新的单调序列，并且此序列长度大于之前An的长度；

2.a(n+1)<=a(n)。此时，a(n+1）当然不可以添加到An序列的尾部。

经过分析，我们可以得出这样的结论：一个单调序列与其后面元素的关系仅与此序列的末尾元素有关。

如此，便有了此题如下的dp解法：

建立一个一维数组dp[ ]，用dp[i]保存长度为i的单调子序列的末尾元素的值，用top保存单调子序列的最大长度。

初始top=1，dp[1]=a1；

然后，我们从前向后遍历序列An（i : 2~n)。显然，我们会遇到两种情况：

1.a[i] > dp[top]。此时，我们把a[i]加入到长度为top的单调序列中，这时序列长度为top+1，top值也跟着更新，即dp[++top] = a[i]；

2.a[i]<=dp[top]。此时，a[i]不能加入长度为top的单调序列，那它应该加入长度为多少的序列呢？

做法是，从后向前遍历dp[ ] (j: top-1~1)，直到满足条件 a[i] > dp[j]，此时，类似于步骤1，我们可以把a[i]加入到长度为j的单调序列中，这时此序列长度为j+1，

我们将dp[j+1]的值更新为a[i]。可是，为什么要更新它呢？

因为a[i]一定小于dp[j+1]。为什么呢？如果a[i]不小于dp[j+1]，我们找到的j就应该是j+1而不是j。那么，我们为什么要保留把dp[j+1]的最小值呢？

因为对于相同长度的单调递增序列来说，末尾元素的值越小，其后元素加入此序列的可能性越大，也就是说，我们这样做，是为了防止丢失最优解。

其中的奥妙，读者可以自己写一两组数据按照上面的步骤体验下，别出太弱的数据哦。O(∩_∩)O

于是，我们很容易写出时间复杂度为O(n*n)的代码，如下：

#include <stdio.h>
#include <string.h>
int main()
{
    int z,n,num[21],dp[21];
    scanf("%d",&z);
    while(z--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&num[i]);
        int top=1;
        dp[1]=num[0];
        for(int i=1;i<n;i++)
        {
            if(num[i] > dp[top])
            {
                dp[++top] = num[i];
            }
            else
            {
                int j;
                for(j=top-1;j>=1;j--)
                    if(num[i] > dp[j])
                        break;
                dp[j+1] = num[i];
            }
        }
        printf("%d\n",top);
    }
    return 0;
}

我们已经得出了答案，那么，我们能不能继续优化下时间复杂度呢？

第一种情况显然不需要优化，那么，第二种情况可不可以呢？

在第二种情况的时候，我们需要做的是：在单调序列dp[ ]中找出一个最大的j，使其满足a[i] > dp[j]，看到“单调”你想到了什么？没错，是二分。

如此，时间复杂度变为(N*logN)；

 
#include <stdio.h>
#include <string.h>
int BinarySearch(int *a,int left,int right,int x)    //返回递增序列a[]中第一次a[i]>=x的位置
{
    if(a[left] >= x)
        return left;
    while(left <= right)
    {
        int mid = (left+right)/2;
        if(a[mid] >= x)
            right = mid-1;
        else
        {
            left = mid+1;
            if(a[left] >= x)
                return left;
        }
    }
}
int main()
{
    int z,top,dp[10005];
    char num[10005];
    scanf("%d",&z);
    while(z--)
    {
        scanf("%s",num);
        dp[(top=1)]=num[0];
        int n=strlen(num);
        for(int i=1;i<n;i++)
        {
            if(num[i] > dp[top])
                dp[++top]  = num[i];
            else
                dp[BinarySearch(dp,1,top,num[i])] = num[i];
        }
        printf("%d\n",top);
    }
    return 0;
}

今天心情不爽，写篇博客静下。如果写的不好，还请大牛们见谅。