• <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
            精品久久久久香蕉网| 国产成人综合久久精品尤物| 精品久久久久久国产牛牛app | 亚洲国产成人久久综合区| 亚洲欧美一级久久精品| 久久九九兔免费精品6| 国产高清美女一级a毛片久久w| 久久精品国产亚洲Aⅴ香蕉| 国产成人精品久久一区二区三区 | 国产精品日韩欧美久久综合| 区久久AAA片69亚洲| 一本一本久久a久久精品综合麻豆| 亚洲精品乱码久久久久久 | 久久久久亚洲AV综合波多野结衣| 久久综合亚洲鲁鲁五月天| 久久久久女人精品毛片| 久久综合九色综合网站| 久久伊人精品一区二区三区| 日本免费久久久久久久网站| AAA级久久久精品无码片| 亚洲欧美精品一区久久中文字幕| 精品久久777| 久久精品国产亚洲5555| 国产一久久香蕉国产线看观看| 狠狠色噜噜色狠狠狠综合久久| 久久久久久久久久久精品尤物| 色综合久久最新中文字幕| 国产成年无码久久久久毛片| 人妻无码αv中文字幕久久琪琪布| 思思久久好好热精品国产| 国产69精品久久久久9999APGF | 亚洲精品无码久久久久AV麻豆| 国产精品伊人久久伊人电影 | 久久91精品国产91久久小草| 亚洲国产另类久久久精品| 精品一二三区久久aaa片| 久久综合视频网| 亚洲国产精品无码久久SM| 中文字幕无码免费久久| 久久久久AV综合网成人| 1000部精品久久久久久久久|