Sequence two |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 98 Accepted Submission(s): 46 |
|
Problem Description
Search is important in the acm algorithm. When you want to solve a problem by using the search method, try to cut is very important.
Now give you a number sequence, include n (<=100) integers, each integer not bigger than 2^31, you want to find the first P subsequences that is not decrease (if total subsequence W is smaller than P, than just give the first W subsequences). The order of subsequences is that: first order the length of the subsequence. Second order the subsequence by lexicographical. For example initial sequence 1 3 2 the total legal subsequences is 5. According to order is {1}; {2}; {3}; {1,2}; {1,3}. If you also can not understand , please see the sample carefully. |
|
Input
The input contains multiple test cases.
Each test case include, first two integers n, P. (1<n<=100, 1<p<=100000). |
|
Output
For each test case output the sequences according to the problem description. And at the end of each case follow a empty line.
|
|
Sample Input
3 5 1 3 2 3 6 1 3 2 4 100 1 2 3 2 |
|
Sample Output
1 2 3 1 2 1 3 1 2 3 1 2 1 3 1 2 3 1 2 1 3 2 2 2 3 1 2 2 1 2 3
Hint
Hint : You must make sure each subsequence in the subsequences is unique
分析:
（1）这道题和前一题sequence one 属于一类题，都是dfs,这里主要是首先排一次顺序，然后再检查时注意输入时的下标，生成的子串不能够出现下表非递增的，也就是首先子串时递增的，其次下标也是递增的，然后不能有重复的子串出现。
（2）这是我的代码，和前一题的代码有稍微的改动，无奈一直wrong。。。。。。。。。。。。哪位研究这一题的看到了，帮忙找找错。。。。。。。。。
|
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; //len:搜索的长度,count:记录有多少个串了 int n,p,len,count_num,pre; //做一个标记，如果一个短的串都不能够找到， //那么就长的串就更不可能找到了，这里的一个巧妙地剪枝如果没用就会超时 bool flag; typedef struct { int n,pos; int ind; }Tem; Tem tem[1001]; Tem num[1001]; bool cmp(Tem a,Tem b) { if(a.n==b.n) return a.pos<b.pos; return a.n<b.n; } //若在产生序列的前一个数字到当前这个数字中， //出现等于num[e]的，那么说明之前已经有序列选择了num[e]， bool check(int s,int e) { for(int i = e-1; i > s; i--) if(num[i].n==num[e].n)return false; return true; } void print_sequence(int length) { for(int i = 0; i < length-1;i++) printf("%d ",tem[i].n); printf("%d\n",tem[length-1].n); } //dep：搜索的深度，也就是目前搜索到子串的长度 //pos: 当前搜索的位置 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&&num[i].pos>tem[dep-1].pos)||dep==0) { if(dep==0&&!check(-1,i)) continue; if(dep!=0&&!check(tem[dep-1].ind,i)) continue; tem[dep].n = num[i].n; tem[dep].pos = num[i].pos; tem[dep].ind = i; dfs(dep+1,i+1); } } return; } int main() { while(scanf("%d%d",&n,&p)!=EOF) { for(int i=0;i<n;i++) { scanf("%d",&num[i].n); num[i].pos = i; } sort(num,num+n,cmp); count_num = 0; for(int i = 1;i < n;i++) { flag=false; pre = 0; len = i; dfs(0,0); if(count_num>=p||!flag)break; } printf("\n"); } return 0; }
这是我从网上找到达一个可以通过的代码。。。。。。
思路一样。。。。。。。求解释。。。。。。。
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; int n,p; struct Node { int pos; int v; }; int cont; Node a[110]; int res[10001]; int deep; bool mcmp(const Node& x,const Node& y) { if(x.v != y.v) return x.v < y.v; else return x.pos < y.pos; }; void init() { int i; int tv; cont = 0; Node tnode; for(i = 1;i <= n;i ++) { scanf("%d",&tv); a[i].pos = i;// 把位置作为结构题的一项 a[i].v = tv; } sort(a+1,a+1+n,mcmp);//按照值的大小重排序 } bool dfs(int dep,int sp,int pp)//deepth ,search position , previous position { int i; int prev; bool f = false; if(dep == deep+1) { cont ++; for(i = 1;i < dep;i ++) printf(i == deep ? "%d\n" : "%d ",res[i]); if(cont == p) return true; return false; } if(sp > n ) return false; for(i = sp;i <= n;i ++) { if(a[i].pos > pp) { if(!f) { f = true; prev = a[i].v;} // 判重 else if(prev == a[i].v) continue;//判重 prev = a[i].v; res[dep] = a[i].v; if(dfs(dep+1,i+1,a[i].pos) ) return true; } } return false; } void work() { int i,j; for(i = 1;i <= n;i ++) { deep = i; if(dfs(1,1,0)) return ; } } int main() { while(scanf("%d%d",&n,&p) != EOF) { init(); work(); printf("\n"); } return 0; }
