• <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
            色欲久久久天天天综合网| 无码AV波多野结衣久久| 久久综合欧美成人| 狠狠精品久久久无码中文字幕 | 亚洲国产成人久久一区久久| 色悠久久久久久久综合网| 蜜臀av性久久久久蜜臀aⅴ| 日韩亚洲欧美久久久www综合网 | 日韩人妻无码精品久久免费一| 久久精品九九亚洲精品| 久久精品国产精品亜洲毛片| 午夜人妻久久久久久久久| 久久激情亚洲精品无码?V| 人妻精品久久无码区| 久久精品国产99久久久香蕉| 欧洲成人午夜精品无码区久久| 久久国产成人精品国产成人亚洲| 亚洲中文精品久久久久久不卡| 国产亚洲美女精品久久久| 欧美牲交A欧牲交aⅴ久久| 久久影院亚洲一区| 一本色道久久88加勒比—综合| 久久夜色精品国产噜噜噜亚洲AV| 亚洲?V乱码久久精品蜜桃 | 国产精品美女久久久免费| 精品国产乱码久久久久久1区2区| 久久笫一福利免费导航| 久久乐国产精品亚洲综合| 日本免费一区二区久久人人澡| 久久亚洲日韩精品一区二区三区| 欧美亚洲日本久久精品| 国产99久久九九精品无码| 久久精品国产精品亚洲精品| 久久无码人妻一区二区三区| 国产亚洲美女精品久久久2020| 久久久久免费视频| 欧美激情精品久久久久久| 久久精品综合一区二区三区| 国产成人久久久精品二区三区| 99久久精品免费看国产| 99久久伊人精品综合观看|