LIS学习以及模板

模板

先帖模板
nlogn:

int stack[10010];  
int lis(int arr[],int n)  
{  
    int i,top,mid,low,high;  
    top = 0;  
    stack[0] = -1;  
    for(i=0;i<n;i++)  
    {  
        if(arr[i]>stack[top])  
            stack[++top] = arr[i];  
        else  
        {  
            low = 1;  
            high = top;  
            while(low <= high)  
            {  
                mid = (low + high)/2;  
                if(arr[i] > stack[mid])  
                    low = mid + 1;  
                else  
                    high = mid - 1;  
            }  
            stack[low] = arr[i];  
        }  
    }  
    return top;  
}  

此模板只能用于计算最长长度，无法打印序列。

n^2

unsigned int LISS(const int array[], size_t length, int result[])  
{  
    unsigned int i, j, k, max;  
    //变长数组参数，C99新特性，用于记录当前各元素作为最大元素的最长递增序列长度  
    unsigned int liss[length];  
    //前驱元素数组，记录当前以该元素作为最大元素的递增序列中该元素的前驱节点，用于打印序列用  
    unsigned int pre[length];  
    for(i = 0; i < length; ++i)  
    {  
        liss[i] = 1;  
        pre[i] = i;  
    }  
    for(i = 1, max = 1, k = 0; i < length; ++i)  
    {  
        //找到以array[i]为最末元素的最长递增子序列  
        for(j = 0; j < i; ++j)  
        {  
            //如果要求非递减子序列只需将array[j] < array[i]改成<=，  
            //如果要求递减子序列只需改为>  
            if(array[j] < array[i] && liss[j] + 1> liss[i])  
            {  
                liss[i] = liss[j] + 1;  
                pre[i] = j;  
                //得到当前最长递增子序列的长度，以及该子序列的最末元素的位置  
                if(max < liss[i])  
                {  
                    max = liss[i];  
                    k = i;  
                }  
            }  
        }  
    }  
    //输出序列  
    i = max - 1;  
    while(pre[k] != k)  
    {  
        result[i--] = array[k];  
        k = pre[k];  
    }  
    result[i] = array[k];  
    return max;  
}

此模板需要解释的地方是最后的输出序列，（其实就像链表
最开始的pre[0] = 0，其他的pos都跟pre[pos]不一样，因为肯定是有一个最长递增序列的。所以我们就要从后往前记录，这样才能用res数组顺序输出。

hdu 1160 fatmouse
题意：
一个耗子两个属性，一个体重，一个速度，我们要找一个最长的体重严格递增，速度严格递减的序列。
思路：
先对体重进行排序，然后对速度求lis
坑：开始的时候进行debug的时候，没有考虑体重也需要严格递增，其实判断的时候需要加体重严格递增的限制条件，恩。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
    int p;
    int w,s;
}m[1005];
bool cmp(struct node a,struct node b)
{
    return a.w < b.w;
}
int pre[1005];
int lis[1005];
int res[1005];
int main()
{
    int cnt = 0;
    while (scanf("%d%d",&m[cnt].w,&m[cnt].s) != EOF)
    {
        m[cnt].p = cnt;
        cnt++;
    }
    sort(m,m+cnt,cmp);
    for (int i  = 0;i < cnt;i++)
    {
        pre[i] = i;
        lis[i] = 1;
    }
    int len = 1,pos = 0;
    for (int i = 0;i < cnt;i++)
    {
        for (int j = 1;j < i;j++)
        {
            if (m[j].s > m[i].s && lis[j] + 1 > lis[i] && m[j].w < m[i].w)
            {
                pre[i] = j;
                lis[i] = lis[j] + 1;
                if (lis[i] > len)
                {
                    len = lis[i];
                    pos = i;
                }
            }
        }
    }
    int i = len - 1;
    while (pre[pos] != pos)
    {
        res[i--] = m[pos].p;
        pos = pre[pos];
    }
    res[i] = m[pos].p;
    printf("%d\n",len);
    for (int j = i;j < len;j++)
        printf("%d\n",res[j] + 1);
    return 0;
}

hdu 1950 插头
题意：
2333，没有看懂，看图以及看样例（反正线不能交叉，裸的lis
思路：
nlogn的算法，因为只是求最长的长度。
代码：

#include <stdio.h>
#include <string.h>
int a[40005];
int s[40005];
int lis(int n)
{
    int low,high,mid,top = 0;
    s[0] = -1;
    for (int i = 0;i < n;i++)
    {
        if (a[i] > s[top])
            s[++top] = a[i];
        else
        {
            low = 1,high = top;
            while (low <= high)
            {
                mid = (low + high) >> 1;
                if (a[i] > s[mid]) low = mid + 1;
                else high = mid - 1;
            }
            s[low] = a[i];
        }
    }
    return top;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        for (int i = 0;i < n;i++)
            scanf("%d",a+i);
        int ans = lis(n);
        printf("%d\n",ans);
    }
    return 0;
}