• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            gzwzm06

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              1 隨筆 :: 52 文章 :: 17 評(píng)論 :: 0 Trackbacks
            先求出最長(zhǎng)非遞增子序列和最長(zhǎng)非遞減子序列,由總長(zhǎng)度減去其中較長(zhǎng)的一個(gè)
             1#include <cstdio>
             2#include <algorithm> 
             3#include <vector> 
             4#include <list> 
             5#include <iterator> 
             6#include <limits>
             7using namespace std;
             8
             9const int SIZE = 30010;
            10
            11template<typename T>
            12int LIS(T Array[], int nCnt)
            13{
            14    if (nCnt == 0)
            15        return 0;
            16
            17    Array[nCnt++= numeric_limits<T>::max();
            18    
            19    T *= Array;
            20    vector<T> dp;
            21    dp.push_back(p[0]);
            22    int nRet = 1;
            23    for (int n = 1; n < nCnt; ++n)
            24    {
            25        T& e = p[n];
            26        typename vector<T>::iterator itor = upper_bound(dp.begin(), dp.end(), e, less<int>());
            27
            28        if ( itor == dp.end() )
            29            dp.push_back(e);
            30        else if (*itor > e)
            31            *itor = e;        
            32    }

            33
            34    return ((int)dp.size() - 1) ;
            35}

            36
            37template<typename T>
            38int LDS(T Array[], int nCnt)
            39{
            40    Array[nCnt++= numeric_limits<T>::min();
            41
            42    T *= Array;
            43    vector<T> dp;
            44    dp.push_back(p[0]);
            45    int nRet = 1;
            46    for (int n=1; n < nCnt; ++n)
            47    {
            48        T& e = p[n];
            49        typename vector<T>::iterator itor = upper_bound(dp.begin(), dp.end(), e, greater<int>());    
            50        
            51        if ( itor == dp.end() )
            52            dp.push_back(e);
            53        else if (*itor < e)
            54            *itor = e;        
            55    }

            56
            57    return (int)dp.size()-1;
            58}

            59
            60int array[SIZE];
            61
            62int main()
            63{
            64    int i, n, lis, lds;
            65
            66    scanf("%d"&n);
            67
            68    for ( i = 0; i < n; ++i )
            69    {
            70        scanf("%d"&array[i]);
            71    }

            72
            73    lis = LIS(array, n);
            74    lds = LDS(array, n);
            75
            76    int ans = (lis > lds ? lis : lds);
            77
            78    printf("%d\n", n - ans);
            79    return 0;
            80}
            posted on 2009-03-22 19:55 閱讀(891) 評(píng)論(0)  編輯 收藏 引用 所屬分類: DP
            91精品观看91久久久久久| 99久久精品国产毛片| 性做久久久久久久久浪潮| 色悠久久久久久久综合网 | 精品国产VA久久久久久久冰| 精品国产乱码久久久久久郑州公司| 91性高湖久久久久| 欧美日韩久久中文字幕| 久久电影网一区| 99精品国产99久久久久久97| 国产亚洲色婷婷久久99精品91| 久久99精品国产麻豆宅宅| 品成人欧美大片久久国产欧美| 国内精品久久久久久久久电影网| 久久免费高清视频| 亚洲AV日韩精品久久久久久久 | 国产精品久久久久久久久软件| 久久精品人人做人人爽97| 一本久久免费视频| 国产激情久久久久影院老熟女免费| 久久婷婷是五月综合色狠狠| 久久亚洲精品国产精品| 国产69精品久久久久9999| 日本久久久久亚洲中字幕| 久久精品国产一区二区三区| 久久亚洲国产中v天仙www| 99蜜桃臀久久久欧美精品网站 | 国产精品久久久久aaaa| 亚洲国产精品无码成人片久久| 欧美色综合久久久久久| 天天爽天天爽天天片a久久网| 99久久婷婷国产综合亚洲| 综合久久国产九一剧情麻豆| 久久综合色老色| 久久精品综合网| 久久精品国产精品亚洲精品| 蜜桃麻豆www久久国产精品| 国产呻吟久久久久久久92| 国产免费久久精品99久久| 精品久久久久久99人妻| 久久精品国产黑森林|