假设有排序的个数为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