HDU 2611 Sequence two （dfs + 重判 + 剪枝）

迷南。 2024-02-17 19:11 23阅读 0赞

2610 按照长度优先 位置次之 输出所有不递减序列

2611 按照长度优先 大小次之 输出所有不递减序列，2610的加强版

思路：本题的重判和剪枝方法和2610的基本不变，不再累述；首先按照长度输出，然后当长度相同时，按照字典序最小输出（因此用sort对序列进行排序）此时要特别注意，输出的子序列元素位置对应于原序列的位置下标一定要保证是递增的，所以用结构体来存储值和下标。本题还需要注意的问题是第二种判重（见2610题解），在判重的时候不能在排好序的数组中判重，应该在原数组中遍历，看是否已经出现过当前数字，因为你在排好序的数组中这样判重的话，会把一些合法的答案弃掉了（本题的关键）。

比如原序列1 2 3 2 3 排好序后是1 2 2 3 3，现在搜长度为4的子串，已搜1 2 2 ，现在搜第四个3，发现第四个数3在原数组中的位置是3 < 第3个数2在原数组中的位置4，不合法，弃之，然后搜第5个3，现在执行第二种判重，如果在排好序的数组中判重的话，就会发现第四个位置有了3，于是也会放弃这组，而实际情况是，1 2 2 3 是合法的！所以要在第三个2在原数组的位置4开始，到第五个数3在原数组的位置5之间看有没有3出现，显然是没有的，所以1 2 2 3 合法。

两道经典搜索题hdu2610 2611

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=100+10;
    struct node{
    	int t; //值 
    	int pos;  //对应序列中的位置 
    }son[maxn],order[maxn];  //子序列、输入序列 
    int yuan[maxn];   //原序列 
    int n,p;
    int len,count1; //当前子序列长度、输出的子序列个数 
    bool flag;    //剪枝判断 
    bool cmp(const node& n1,const node& n2){ //用于sort的排序函数 
    	    if(n1.t!=n2.t)
    		return n1.t<n2.t;
    		return n1.pos<n2.pos;
    	}
    void print(){
    	for(int i=0;i<len-1;i++)printf("%d ",son[i].t);
    	printf("%d\n",son[len-1].t);
    }
    bool check1(int p1,int p2){        //当前搜索元素是子序列的第一个时用check1 
    	for(int i=p1;i<p2;i++)
    	if(order[i].t==order[p2].t)return false;
    	return true;
    } 
    bool check2(int p1,int p2){  //前搜索元素不是子序列的第一个时用check2
    	for(int i=p1;i<p2;i++)
    	if(yuan[i]==yuan[p2])return false;
    	return true;
    } 
    void dfs(int deepth,int pos){
    	if(count1>=p)return ;
    	if(deepth==len){
    		print();
    		count1++;
    		flag=false;
    		return ;
    	}
    	for(int i=pos;i<n;i++){
    		if(deepth==0 && !check1(0,i))continue;
    		if(deepth>=1 && (!check2(son[deepth-1].pos+1,order[i].pos) || son[deepth-1].pos>order[i].pos))continue;
    		son[deepth].pos=order[i].pos;
    		son[deepth].t=order[i].t;
    		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].t);
    		order[i].pos=i;
    		yuan[i]=order[i].t;
    		}
    		sort(order,order+n,cmp);
    		count1=0;
    		for(int i=0;i<n;i++){
    			len=i+1;
    			flag=true;
    			dfs(0,0);
    			if(flag)break;  //剪枝（列如当len=3时无解，那么>3就肯定不满足了） 
    		printf("\n");
    		}
    	}
    }