题目大意：在给定的序列中找到固定个数的递增的子序列，如果子序列的总个数少于要求的个数，那么就把所有的子序列输出即可。
题解：本来题目也不太看得懂，在别人的博客看了许久才懂，剪枝和判重也不大会，于是暂时先把它给看懂。一个有效的剪枝，一个子串如果不成立，那么比其大的子串显然不成立，所以剪枝。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68 |
#include <cstdio>#include <iostream>#include <cstdlib>#include <algorithm>using
namespace std;int n,p,len,count_num;int num[1001];bool
flag;typedef
struct{ int
n,pos;}Tem;Tem tem[1001];bool
check(int
s,int e){ for(int
i = s+1; i < e; i++) if(num[i]==num[e])return
false; return
true;}void
print_sequence(int
length){ for(int
i = 0; i < length-1;i++) cout<<tem[i].n<<" "; cout<<tem[length-1].n<<endl;}void
dfs(int
dep,int
pos){ if(count_num >= p)return; if(dep==len) { count_num++; flag = true; print_sequence(len); return; } for(int
i=pos;i<n;i++) { if((dep!=0&&tem[dep-1].n<=num[i])||dep==0) { if(dep==0&&!check(-1,i)) continue; if(dep!=0&&!check(tem[dep-1].pos,i)) continue; tem[dep].n = num[i]; tem[dep].pos = i; dfs(dep+1,i+1); } } return;}int
main(){ while(cin>>n>>p) { for(int
i=0;i<n;i++) cin>>num[i]; count_num = 0; for(int
i = 1;i < n;i++) { flag=false; len = i; dfs(0,0); if(count_num>=p||!flag)break; } cout<<endl; } return
0;} |
原文：http://www.cnblogs.com/forever97/p/3543342.html