• <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++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks
            先求出最長非遞增子序列和最長非遞減子序列,由總長度減去其中較長的一個
             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 閱讀(889) 評論(0)  編輯 收藏 引用 所屬分類: DP
            欧美伊人久久大香线蕉综合69| 天天久久狠狠色综合| 久久久久亚洲av无码专区| 久久久噜噜噜www成人网| 亚洲国产精品无码久久久秋霞2| 日本三级久久网| 国产日韩久久久精品影院首页| 91精品国产高清91久久久久久| 久久精品国产亚洲AV嫖农村妇女 | 久久AV高清无码| 久久精品a亚洲国产v高清不卡 | 亚洲国产日韩综合久久精品| 色偷偷88欧美精品久久久| 亚洲色欲久久久综合网东京热| 日韩精品久久无码中文字幕| 久久精品国产精品青草| 久久免费大片| 久久这里只精品国产99热| 亚洲а∨天堂久久精品9966| 久久天堂AV综合合色蜜桃网| 激情综合色综合久久综合| 久久婷婷五月综合色高清| 亚洲精品99久久久久中文字幕| 亚洲午夜久久久影院伊人| 久久久久无码专区亚洲av| 91精品国产91久久| 精品久久久久久中文字幕| 亚洲乱码精品久久久久..| 国产精品乱码久久久久久软件| 嫩草影院久久99| 无码AV中文字幕久久专区| 久久久久久精品免费看SSS| 久久e热在这里只有国产中文精品99 | 国产香蕉97碰碰久久人人| 少妇久久久久久被弄到高潮 | 18岁日韩内射颜射午夜久久成人| 国产精品丝袜久久久久久不卡| 丁香色欲久久久久久综合网| 久久久久久毛片免费看| 久久久精品一区二区三区| 久久国产精品成人片免费|