首页 > 代码库 > hdu 2610
hdu 2610
Sequence one
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 445 Accepted Submission(s): 167
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 (<=1000) 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 sequence of each integer’s position in the initial sequence. For example initial sequence 1 3 2 the total legal subsequences is 5. According to order is {1}; {3}; {2}; {1,3}; {1,2}. {1,3} is first than {1,2} because the sequence of each integer’s position in the initial sequence are {1,2} and {1,3}. {1,2} is smaller than {1,3}. If you also can not understand , please see the sample carefully.
Now give you a number sequence, include n (<=1000) 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 sequence of each integer’s position in the initial sequence. For example initial sequence 1 3 2 the total legal subsequences is 5. According to order is {1}; {3}; {2}; {1,3}; {1,2}. {1,3} is first than {1,2} because the sequence of each integer’s position in the initial sequence are {1,2} and {1,3}. {1,2} is smaller than {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<=1000, 1<p<=10000).
Each test case include, first two integers n, P. (1<n<=1000, 1<p<=10000).
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 51 3 23 61 3 24 1001 2 3 2
Sample Output
1321 31 21321 31 21231 21 32 32 21 2 31 2 2
Hint
Hint : You must make sure each subsequence in the subsequences is unique.
Author
yifenfei
好题:
判重很巧妙
重判,这里有两个重判,第一个重判是判断如果搜索的是子序列的第一个元素,那么判断从原始序列开始到当前位置是否已经出现过该元素,若出现过则之前肯定搜索过该元素,则放弃该元素的搜索。第二个重判,当搜索的不是子序列的第一个元素时,则判断子序列的前一个元素对应原始序列的位置,然后从该位置下一个元素开始到到当前搜索的位置之前判断该元素是否出现过,如果出现过,说明该子串出现过重复的,则放弃该元素。
dep代表 子串的长度,pos代表 原数组中的位置。
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<string>#include<algorithm>#include<queue>#include<vector>#include<set>using namespace std;int n,p,a[1010],cnt,len;bool flag;struct line{ int num; int pos;}path[1010];bool check(int x,int y){ for(int i=x;i<y;i++) { if(a[i]==a[y]) return false; } return true;}void dfs(int dep,int pos){ if(cnt>=p) return ; if(dep==len) { cnt++; flag=true; for(int i=0;i<len-1;i++) printf("%d ",path[i].num); printf("%d\n",path[len-1].num); return ; } for(int i=pos;i<n;i++) { if(dep==0||path[dep-1].num<=a[i]) { if(dep==0&&!check(0,i)) continue; if(dep!=0&&!check(path[dep-1].pos+1,i)) continue; path[dep].num=a[i]; path[dep].pos=i; dfs(dep+1,i+1); } }}int main(){ while(scanf("%d%d",&n,&p)!=EOF) { cnt=0; for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { len=i; flag=false; dfs(0,0); if(!flag||cnt>=p) break; } printf("\n"); } return 0;}
hdu 2610
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。