HDU 2610 Sequence one(dfs+剪枝)

题意：给出一个序列找满足条件的子序列：非递减+长度+位置

两个重判：如果当前搜索元素是子序列的第一个元素时，从原始序列的初始位置开始到当前位置，如果当前元素已经出现过了，就不在搜索此元素了（肯定被搜索过了）

                ：如果当前搜索元素不是子序列的第一个元素时，找到子序列中前一个元素对应原始序列的位置，从该位置的下一个到当前元素的位置，如果当前元素已经出现过了，就不在搜索此元素了（肯定被搜索过了）。

剪枝：如果搜索到长度len没有一个满足条件的解，那么大于此长度的也肯定不满足，故应减掉。

#include<cstdio>#include<cstring>using namespace std;const int maxn=1000+10;int order[maxn];    //存储输入序列 struct node{	int pos,t;    //当前数字t对应序列order中的位置pos }nt[maxn]; int n,p;int len,count1;      //当前长度和输出的序列个数 bool flag;           // 剪枝判断（若当前长度len没有一个满足解的，那么>len的肯定不满足了，故减掉） void PRint(){	for(int i=0;i<len-1;i++)printf("%d ",nt[i].t);	printf("%d/n",nt[len-1].t); }bool check(int p1,int p2){     	for(int i=p1;i<p2;i++){		if(order[i]==order[p2])return false;	}	return true;}void dfs(int deepth,int pos){       //当前子序列中的元素个数deepth,及在order序列中的位置 	if(count1>=p)return ;	if(deepth==len){		print();		count1++;		flag=false;		return ;	}	for(int i=pos;i<n;i++){		if(deepth==0 &&!check(0,i))continue;    //如果是当前元素都是子序列的第一个 		if(deepth>0 && (!check(nt[deepth-1].pos+1,i) || nt[deepth-1].t>order[i]))continue;      //要满足非递减		nt[deepth].pos=i;		nt[deepth].t=order[i];		dfs(deepth+1,i+1);		}	}int main(){	while(scanf("%d%d",&n,&p)==2){		for(int i=0;i<n;i++)scanf("%d",&order[i]);		count1=0; 		ok=false;		for(int i=0;i<n;i++){			len=i+1;			flag=true;			dfs(0,0);		    if(flag)break;        //剪枝 		}		printf("/n");	}	return 0;}