[DFS+소 작 동 판정 중][HDU 2610+HDU 2611]Sequence

제목 2610 길이 우선 위치 에 따라 출력 하지 않 는 모든 시퀀스
         2611 길이 의 우선 크기 에 따라 출력 모든 감소 하지 않 는 시퀀스
해제http://www.cnblogs.com/wally/archive/2013/05/12/3074356.html
제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=2610
http://acm.hdu.edu.cn/showproblem.php?pid=2611、
좋 은 두 개의 검색 문 제 는 모두 판 중 을 사 용 했 습 니 다...orz......................................................................무릎 꿇 는 소
큰 소의 hdu 2610 사고:제목 은 간단 하 다.주어진 서열 에서 고정된 개수 의 증가 하 는 하위 서열 을 찾 는 것 이다.만약 에 하위 서열 의 총 갯 수가 요구 하 는 갯 수 보다 적 으 면 모든 하위 서열 을 출력 하면 된다.각 조 의 테스트 사례 가 빈 줄 이 되도록 주의해 야 한다.
기교 1:중 판,여기 두 개의 중 판 이 있 습 니 다.
첫 번 째 재판 은 하위 시퀀스 의 첫 번 째 요 소 를 검색 했다 면 원본 시퀀스 부터 현재 위치 까지 이 요소 가 나 타 났 는 지 판단 하 는 것 입 니 다.나 타 났 다 면 이 요 소 를 검색 한 적 이 있 을 것 이 고 이 요소 의 검색 을 포기 하 는 것 입 니 다.두 번 째 재판 은 하위 서열 의 첫 번 째 요소 가 아 닌 것 을 검색 할 때 하위 서열 의 이전 요소 가 원시 서열 에 대응 하 는 위 치 를 판단 한 다음 에 이 위치 에서 다음 요소 부터 현재 검색 한 위치 까지 이 요소 가 나 타 났 는 지 판단 하고 나 타 났 다 면 이 하위 문자열 이 중복 되 었 다 는 것 을 설명 하면 이 요 소 를 포기 합 니 다.이곳 의 두 재심 은 잘 생각해 야 한다.매우 교묘 하 다.
기술 2:가지치기,여기 가지치기 기술 은 표 시 를 하 는 것 입 니 다.만약 에 제 가 길이 가 3 인 하위 꼬치 를 검색 할 때 일치 하 는 것 이 하나 도 없다 는 것 을 발견 하면 길이 가 4 인 하위 꼬치 가 조건 에 부합 되 는 것 이 존재 할 수 없습니다.만약 이 가지치기 가 없다 면 시간 을 초과 할 것 이 니,보아하니 영향 이 매우 큰 것 같다.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
struct Node{
    int num,pos;
}path[MAXN];

int num[MAXN];
int n,p,_count,len;
bool flag;

bool Judge(int st,int ed){
    for(int i=st;i<ed;i++){
        if(num[i]==num[ed])return false;
    }
    return true;
}

void dfs(int l,int pos){
    if(_count>=p)return ;
    if(l==len){
        _count++;
        flag=true;
        for(int i=0;i<l-1;i++){
            printf("%d ",path[i].num);
        }
        printf("%d
",path[l-1].num);
        return ;
    }
    for(int i=pos;i<n;i++){
        if((l!=0&&path[l-1].num<=num[i])||l==0){
            if(l!=0&&!Judge(path[l-1].pos+1,i))continue;
            if(l==0&&!Judge(0,i))continue;
            path[l].num=num[i];
            path[l].pos=i;
            dfs(l+1,i+1);
        }
    }
}


int main(){
    while(~scanf("%d%d",&n,&p)){
        for(int i=0;i<n;i++)
            scanf("%d",&num[i]);
        _count=0;
        for(int i=1;i<n;i++){
            flag=false;
            len=i;
            dfs(0,0);
            if(_count>=p||(!flag))break;
        }
        puts("");
    }
    return 0;
}

hdu 2611 문제 설명:앞의 문제 sequence one 은 같은 문제 에 속 합 니 다.모두 dfs 입 니 다.먼저 한 번 순 서 를 정 한 다음 에 검사 할 때 입력 할 때의 아래 표 시 를 주의 하 십시오.생 성 된 하위 열 은 다음 표 가 증가 하지 않 는 것 이 나타 나 지 않 습 니 다.즉,먼저 하위 열 이 증가 할 때 증가 하 는 것 입 니 다.그 다음 에 아래 표 도 증가 한 다음 에 중복 되 는 하위 열 이 나타 나 면 안 됩 니 다.
기교:무 게 를 판단 하 는 기교 입 니 다.여기 서 우 리 는 처음에 flag=false 를 설정 할 수 있 습 니 다.첫 번 째 때 이 flag 는 true 이 고 그 다음 에 pre 로 현재 위치의 수 를 보존 한 다음 에 뒤에 같은 len 의 서열 을 검색 할 때 현재 의 수가 pre 와 같다 면 이전에 이미 검색 한 것 을 설명 하고 continue 하면 됩 니 다.그렇지 않 으 면 pre 는 이 수 를 보류 합 니 다.그리고 렌+1 의 수 를...이곳 의 flag 와 pre 는 매우 절묘 하 게 사용 되 었 다.orz...ym!!!

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 110
struct Node{
    int num,pos;
}node[MAXN];
int n,p,len,l,_count;
int path[MAXN];

int cmp(const Node &p,const Node &q){
    if(p.num!=q.num)
        return p.num<q.num;
    return p.pos<q.pos;
}

bool dfs(int l,int pos,int repos){ 
    if(l==len){
        _count++;
        for(int i=0;i<l-1;i++){
            printf("%d ",path[i]);
        }
        printf("%d
",path[l-1]);
        if(_count==p)return true;
        return false;
    }
    int pre;
    bool flag=false;//flag pre     ，     ；
    for(int i=pos;i<=n;i++){
        //                  。
        if(node[i].pos>repos){
            if(!flag){flag=true;pre=node[i].num;}//  
            else if(pre==node[i].num)continue;//  
            pre=node[i].num;//           ，       dfs   ；
            path[l]=node[i].num;
            if(dfs(l+1,i+1,node[i].pos))return true;
        }
    }
    return false;
}



int main(){
    while(~scanf("%d%d",&n,&p)){
        for(int i=1;i<=n;i++){
            scanf("%d",&node[i].num);
            node[i].pos=i;
        }
        sort(node+1,node+n+1,cmp);
        _count=0;
        for(int i=1;i<n;i++){
            len=i;
            if(dfs(0,1,0))break;
        }
        puts("");
    }
    return 0;
}