noi 4977 怪盗基德的滑翔翼

一、demo 最长上升序列

程序见Language C\LIS r1

基本思想

构造两个数组，num放序列内容，seq放以第i个元素为终点的最长上升序列，在seq中找最大值(max_element)即使整个序列的最大值。

步骤

1. seq初始化为1
2. 外循环n次，每次确定以fini为终点的最长子序列seq[fini]
   内循环star从头到fini-1，若num[star]<num[fini]，则start可以作为子序列的一部分(给offer)，要不要呢？以i为终点的最长子序列seq[fini]应该为 seq[star]+1 和原先seq[fini]中的最大值。
3. 从seq中找到最大值

int LIS(int num[],int n)
{
    int seq[100];
    int len = 1;
    int fini,star;
    for(fini=0;fini<n;fini++)
        seq[fini]=1;
    for(fini=0;fini<n;fini++)
    {
        for(star=0;star<fini;star++)
        {
            if(num[star]<=num[fini])       //给offer了
                seq[fini]=max(seq[star]+1,seq[fini]);
        }
    }
    len=*(max_element(seq,seq+n));
    return len;
}

二、NOI4977

分最大上升子序列、最大下降子序列，分别计算，取最大值。
程序见Language C\prepare\noi4977