首页 > 代码库 > hdu 2160 Sequence one(DFS)
hdu 2160 Sequence one(DFS)
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <cstdio> 5 #include <memory.h> 6 using namespace std; 7 #define MAXN 20002 8 9 10 //适用于正整数11 template <class T>12 inline void scan_d(T &ret) {13 char c; ret=0;14 while((c=getchar())<‘0‘||c>‘9‘);15 while(c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘),c=getchar();16 }17 18 int a[1010];19 int cnt;20 int ans[1010];21 int tot;22 int n, k;23 int flag;24 25 int check(int i,int j) //检查是否有出现过的数字26 {27 while (i < j)28 if (a[i++] == a[j])29 return 0;30 return 1;31 }32 33 void dfs(int now, int num)34 {35 int i;36 if (num == tot) {37 ++cnt;38 for (i = 0;i < tot-1; ++ i)39 printf("%d ",ans[i]);40 printf("%d\n",ans[tot-1]);41 if (cnt == k) flag = 1;42 return;43 }44 if (num == 0) { //第一次不存在前一个数,特殊处理45 for (i = 0;i < n; ++ i) {46 if (check(0,i)) {47 ans[num] = a[i];48 dfs(i,1);49 if (flag) return;50 }51 }52 } else {53 for (i = now + 1;i < n; ++ i) {54 if (a[i] >= a[now] && check(now+1,i)) {55 ans[num] = a[i];56 dfs(i,num + 1);57 if (flag) return;58 }59 }60 }61 }62 63 int main()64 {65 int i, t;66 while (~scanf("%d%d",&n,&k)) {67 for (i = 0;i < n; ++ i)68 scan_d(a[i]);69 cnt = 0;70 for (tot = 1;cnt < k; ++ tot) {71 flag = 0;72 t = cnt;73 dfs(0,0);74 if (t == cnt || flag) break; //达到要求个数或者输出完所有可能情况结束75 }76 puts("");77 }78 return 0;79 }
hdu 2160 Sequence one(DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。