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

hdu 2610 Sequence one-DFS-[解题报告]C++

Sequence one

问题描述 :

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.

输入:

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

输出:

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

样例输入:

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

样例输出:

1
3
2
1 3
1 2

1
3
2
1 3
1 2

1
2
3
1 2
1 3
2 3
2 2
1 2 3
1 2 2


Hint
Hint : You must make sure each subsequence in the subsequences is unique.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
const int maxn = 10010;
const int maxm = 1100;
struct node {
	int value;
	int index;
};
node in[maxm];
node ans[maxn];//result;
int n, p;
int cnt = 0;
bool f[maxm];

void print(int len) {
	for(int i = 1; i < len; i++) printf("%d ", ans[i].value);
	printf("%d\n", ans[len].value);
	cnt++;
	if(cnt==p) return;
}

void init() {
    int i, j;
    f[1] = true;
    for(i = 1; i <= n; i++) {
        for(j = 1; j < i; j++) {
            if(in[j].value == in[i].value) {
                break;
            }
        }
        if(j==i) {
            printf("%d\n", in[i].value);
            cnt++;
            if(cnt==p) return;
        }
    }
}

void dfs(int lev, int len)
{
	if(cnt>=p) return;
	if(lev==0) {// process the repeated root
        int i, j;
		for(i = 1; i <= n; i++) {
			for(j = 1; j < i; j++){
				if(in[j].value == in[i].value){
                    break;
				}
			}
            if(j==i) {
                ans[1].value = in[i].value;
                ans[1].index = in[i].index;
                dfs(lev+1, len);
            }
		}
	}
	if(lev==len) {
	    f[len] = true;
		print(len);
		return;
	}
	if(lev>=1) {
		for(int i = ans[lev].index+1; i <= n; i++) {
			if(in[i].value >= ans[lev].value) {
				int mark = true;
				for(int v = ans[lev].index+1; v < in[i].index; v++) {
					if(in[v].value == in[i].value) {
						mark = false;
						break;
					}
				}
				if(mark) {
					ans[lev+1].value = in[i].value;
					ans[lev+1].index = in[i].index;
					dfs(lev+1, len);
				}
			}
		}
	}
}

int main()
{
	while(scanf("%d%d", &n, &p) != EOF) {
		cnt = 0;
		for(int i = 1; i <= n; i++) {
            f[i] = false;
		}
		for(int i = 1; i <= n; i++) {
			scanf("%d", &in[i].value);
			in[i].index = i;
			ans[i].value = in[i].value;
			ans[i].index = i;
		}
		init();//if the len equal 1
		for(int i = 2; i <= n-1; i++) {// get different length
                if(f[i-1]==true) {
                    dfs(0, i);
                }
                else break;
		}
		printf("\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/achiberx/article/details/9748169


,
  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。