首页 > 代码库 > 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)