2014
02-12

# 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

HintHint : 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;
}

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