题意：这题意真的十分费解，看了好久才明白。
给定N个数字，产生p个子序列，序列满足：先按长度排列，而且子序列本身是递增的；之后，按子序列中各个数字所在位置排序。
最主要的就是判重还有“子序列必须满足递增”
具体的解释看代码吧
View Code
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int v,pos;
}ans[1001];
int a[1001],n,p,nnum,total;
bool check(int s,int e)//判重，我觉得是这道题目的关键
{
for(int i=s+1;i<e;i++)//若在产生序列的前一个数字到当前这个数字中，出现等于a[e]的，那么说明之前已经有序列选择了a[e]，
//如果现在选上，则一定会出现跟之前重复的序列
if(a[i]==a[e])
return false;
return true;
}
void dfs(int num,int cur,int len)
{
if(total>=p)
return;
if(num==len)
{
printf("%d",ans[0].v);
for(int i=1;i<num;i++)
printf(" %d",ans[i].v);
puts("");
total++;
nnum++;
return;
}
for(int i=cur;i<n;i++)
{
if((num!=0 && a[i]>=ans[num-1].v) || num==0)//产生的序列要满足递增
{
if(num==0 && !check(-1,i))//这里的俩步判重要细细体味一下，
continue;
if(num!=0 && !check(ans[num-1].pos,i))
continue;
ans[num].v=a[i];
ans[num].pos=i;
dfs(num+1,i+1,len);
}
}
}
int main()
{
while(scanf("%d %d",&n,&p)==2)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
total=0;
for(int i=1;i<=n;i++)//枚举序列的长度
{
nnum=0;
dfs(0,0,i);
if(total>=p || !nnum)//若nnum等于0，则后面也不可能再有序列满足条件了，是否超时的关键
break;
}
puts("");
}
return 0;
}
题意：与上一题类似，产生的序列是一样的，不过要排序，为了避免产生之后再排序，先将给定的序列先排序，这样产生的序列就是有序的了 ，中间为了保证产生的子序列是有序的，需要同时保存各自排序前所在的位置。这样，就可以知道原先的相对位置了。
去重的方法与之前略有不同，因为序列本身是有序的了，就不用遍历去比较了，直接保存前一个即可。
View Code
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int v,pos;
};
node a[101];
int ans[101],n,p,total,len;
bool cmp(node c,node d)
{
if(c.v!=d.v)
return c.v<d.v;
return c.pos<d.pos;
}
void dfs(int num,int cur,int last)//num表示当前序列的长度，cur表示选到了原序列的第cur个元素，last表示上一次选的数字的原始位置
{
if(total>=p)
return;
if(num==len)
{
printf("%d",ans[0]);
for(int i=1;i<num;i++)
printf(" %d",ans[i]);
puts("");
total++;
return;
}
bool flag=false;
int pre;
for(int i=cur;i<n;i++)
{
if(a[i].pos>last)//产生的序列要满足递增
{
if(!flag){//去重，相同的就不选，标记一下
flag=true;
}
else if(a[i].v==pre)
continue;
pre=a[i].v;//pre保存上一个选的数字
ans[num]=a[i].v;
dfs(num+1,i+1,a[i].pos);
}
}
}
int main()
{
while(scanf("%d %d",&n,&p)==2)
{
for(int i=0;i<n;i++)
{
scanf("%d",&a[i].v);
a[i].pos=i;
}
sort(a,a+n,cmp);
total=0;
for(int i=1;i<=n;i++)//枚举序列的长度
{
len=i;
dfs(0,0,-1);
if(total>=p)
break;
}
puts("");
}
return 0;
}