下面两道题目对比思考
Problem w:
Problem Description
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.<br>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. <br>
Input
The input contains multiple test cases.<br>Each test case include, first two integers n, P. (1<n<=1000, 1<p<=10000). <br>
Output
For each test case output the sequences according to the problem description. And at the end of each case follow a empty line.
Sample Input
3 5
1 3 2
3 6
1 3 2
4 100
1 2 3 2
Sample Output
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
题意：
输入n个数，找到p个指定的子序列（递增），输出即可，但输出需按子序列长度和位置(原序列的位置）排列。
枚举子序列长度，一个个深搜；
仔细思考56行上下那部分的意思
举个例子：1 6 7 8 7；
输出三位长度的时候 1 6 7；有两种，那个地方就是为了出现两种1 6 7
code：
//求的是最大不下降子序列
#include<bits/stdc++.h>
using namespace std;
int n,m;
int num[1005];
int ans,maxn;//总个数
bool flag;
struct node
{int x,p;//x表示序列中的元素，p表示每个元素在位置
}s[1005];
void print(int len);
void dfs(int len,int place);
int main()
{while(scanf("%d %d",&n,&m)!=EOF){ans=0;memset(s,0,sizeof(s));for(int i=0;i<n;++i)scanf("%d",&num[i]);for(int i=1;i<=n;++i)//逐个搜索最大值{maxn=i;flag=false;//先假设这一个长度的没有，计算中如果找到这一长度的，改变falgdfs(0,0);if(ans>=m||!flag)break;}printf("\n");}return 0;
}
void dfs(int len,int place)//长度和地点
{int t;//寻找是否有相同元素是用的bool temp;//记录是相同的元素if(ans>=m)return ;if(len==maxn){print(len);return ;}for(int i=place;i<n;++i)if(!len||(len&&s[len-1].x<=num[i]))//判断是否能加上这个数//当前没有数或者当前位置的数大于应该序列中的最后一个数{if(len==0)//特判子序列为0是，否则会数组越界t=0;elset=s[len-1].p+1;//下面的步骤是为了将相同的序列过滤掉temp=false;for(int j=t;j<i;++j)//判断找到的这个元素与上一次找的的元素，它们两之间有没有与当前要插入的元素有相同的{if(num[j]==num[i])temp=true;}if(temp)continue;s[len].x=num[i];s[len].p=i;dfs(len+1,i+1);}}
void print(int len)
{++ans;flag=true;//表示这有这一长度的序列for(int i=0;i<len-1;++i)printf("%d ",s[i].x);printf("%d\n",s[len-1].x);
}
Problem x:
Problem Description
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.<br>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. <br>
Input
The input contains multiple test cases.<br>Each test case include, first two integers n, P. (1<n<=100, 1<p<=100000). <br>
Output
For each test case output the sequences according to the problem description. And at the end of each case follow a empty line.
Sample Input
3 5
1 3 2
3 6
1 3 2
4 100
1 2 3 2
Sample Output
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
题意：
输入n个数，找到p个指定的子序列（递增），输出即可，但输出需按子序列长度和排列。
与上一题不一样的地方是：这一题是相同长度的按照字典顺序排序输出
所以需要sort一遍排序，然后按照位置排序输出
同样这个也需要重判（将相同的序列，去除，代码65行左右）
code：
#include<bits/stdc++.h>
using namespace std;
struct Point
{int num;//原序列中的数字int place;//原序列中的位置
}s[1005];
int save[1005];//储存序列
int n,m;
int maxn;
int ans;
//输出
bool print(int len);
//排序，按照字典（即升序）排序
bool cmp(Point a,Point b);
//搜索
bool dfs(int len,int place,int re);
int main()
{while(scanf("%d%d",&n,&m)!=EOF){ans=0;//memset(s,0,sizeof(s));//memset(save,0,sizeof(save));for(int i=0;i<n;++i){scanf("%d",&s[i].num);s[i].place=i;//记录位置}sort(s,s+n,cmp);for(int i=1;i<=n;++i){maxn=i;//按照个数搜索if(dfs(0,0,-1))//剪枝，当所有序列全输出时，结束break;}printf("\n");}return 0;
}
bool cmp(Point a,Point b)
{return a.num==b.num?a.place<b.place:a.num<b.num;//以元素大小为首，位置为辅排序
}
bool print(int len)
{for(int i=0;i<len-1;++i)printf("%d ",save[i]);printf("%d\n",save[len-1]);if(ans>=m)//判断是否输出结束return true;;return false;
}
bool dfs(int len,int place,int re)
{if(len==maxn)//满足条件时输出{++ans;if(print(len))return true;elsereturn false;}bool temp=false;//记录第一个数，例如：1 5 6 6//重判：1 5 6，第三个与第四的位置都是6 ，目的是为了不出现两个（1 5 6）int cnt;//辅助for(int i=place;i<n;++i)if(s[i].place>re){if(!temp){temp=true;cnt=s[i].num;}else{if(s[i].num==cnt)continue;}cnt=s[i].num;save[len]=s[i].num;//记录序列if(dfs(len+1,i+1,s[i].place))//深搜return true;}return false;
}