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 阅读(878) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理