HDU 2610 Sequence one(dfs+剪枝)

梦里梦外; 2024-02-17 19:11 16阅读 0赞

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

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

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

剪枝：如果搜索到长度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;
    }