pku + 1989 最短非子序列

假设有排序的个数为n,则其最短的非子序长度,可由下面方法求得。

如果存在其有包括全排序的一个最小组合,(1,2,...n),(次序不限,只要有1...n的数字就行了,也有可能有重复数字)

找到其所有这样组合。可合成()()()...()[],( 设有k个括号,[]里的元素可能为空)
则其最短的非子序长度为k+1;
原因:
长度为k的子序,都可由前k个括号里抽出一个数组成。
但对于k+1,就找不到一个组合,因为最后一个组合里少了需要的最后一个数。

如本例子中:
14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

首先有(1,5,3,2,5,1,3,4)(4,2,5,1,2,3)[]
故其最短非子序长度为3;
 1 #include <iostream>
 2 #include <new>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     //freopen( "in.txt","r",stdin );
10     int n,k;
11     cin >> n;
12     cin >> k;
13     vector<bool> v1( k+1,false );
14     int num = 1;
15     for ( int i = 0,j = 0,k1; i != n; ++i )
16     {
17         cin >> k1;
18         if ( v1[k1] == false )
19         {
20             ++j;
21             v1[k1] = true;
22         }
23         if ( j == k )
24         {
25             j = 0;
26             ++num;
27             for ( int k2 = 0; k2 != v1.size(); ++k2 )
28                 v1[k2] = false;
29         }
30     }
31     cout << num << endl;
32     
33 }
34 
35                 
36 
37 
38 

posted on 2010-06-09 21:39 haozi 阅读(529) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


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


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜