首页 > 搜索 > DFS搜索 > hdu 2611 Sequence two-DFS-[解题报告]C++
2014
02-12

hdu 2611 Sequence two-DFS-[解题报告]C++

Sequence two

问题描述 :

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.

输入:

The input contains multiple test cases.
Each test case include, first two integers n, P. (1<n<=100, 1<p<=100000).

输出:

The input contains multiple test cases.
Each test case include, first two integers n, P. (1<n<=100, 1<p<=100000).

样例输入:

3 5
1 3 2
3 6
1 3 2
4 100
1 2 3 2

样例输出:

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.

点击打开链接

与之前的2610一种噢乖类型,只不过这个要求先按长度,再按字典序。

这个需要对原序列排序,先按小到大,再按位置的先后。。

//给你一个序列,要求找出它的递增子序列,按照长度从小到大,序列元素按字典序
//然后输入前m个子序列
/*
	按照深度一层一层的搜索,如果在寻找该层中满足条件的元素时,
	要判断之前是否出现过(是指之前找该层时是否出现过相等的元素)
	如果之前出现过,continue就可以了。
	没有的话,保留当前位置的值
	比如2 3 3 4
	我们上一层找到2了,这一层先找到3,因为3没出现过所以pre=3;
	然后循环继续,有找到该层中满足情况的一个3(3>=2),因为之前已经出现过一个3了,所以continue就可以了。
	然后继续,找到满足的一个4(4>=2),4之前没出现过,更新pre=4;
*/
#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
#define N 101

int a[N];
int n,m;
struct node 
{
	int n,pos;
}A[N];
int f;
int cnt;
int len;
int path[N];
bool cmp(node a,node b)
{
	if(a.n!=b.n)
	return a.n<b.n;
	return a.pos<b.pos;
}

void print(int len)
{
	int i;
	for(i=0;i<len-1;i++)
		printf("%d ",path[i]);
	printf("%d\n",path[i]);

}
//dep为深度,pos为搜索的位置,repos表示重复的位置
int dfs(int dep,int pos,int repos)
{
	if(dep==len)
	{
		cnt++;
		print(len);
		if(cnt==m)return 1;
		return 0;
	}
	int pre;
	int f=0;
	for(int i=pos;i<=n;i++)
	{
		//子串的下标也是递增的
		if(A[i].pos>repos)
		{
			if(f==0){f=1;pre=A[i].n;}//判重
			//如果相等的话,说明有重的,continue
			else if(pre==A[i].n)continue;//判重
			pre=A[i].n;//如果不相等的话保留当前位置的值
			path[dep]=A[i].n;
			if(dfs(dep+1,i+1,A[i].pos))return 1;
		}
	}
	return 0;
}

int main()
{
	int i;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%d",&A[i].n);
			A[i].pos=i;
		}
		sort(A+1,A+1+n,cmp);
		cnt=0;
		for(i=1;i<n;i++)
		{
			len=i;
			if(dfs(0,1,0))break;
		}
		printf("\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/yangyafeiac/article/details/9860271


,
  1. [email protected]

  2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥