HDU 4620 과일 닌 자 익 스 트림 검색

제목: 제목 은 과일 닌 자 를 묘사 한 것 이다.
N 은 다음 과 같이 모두 N 가지 과일 을 자 르 는 방식 이 있다 고 밝 혔 다.
M 은 네가 썰 어야 할 과일 이 M 개 라 고 표시 했다.
W 는 두 번 의 연속 연 타 사이 의 최대 간격 을 나타 낸다.
그리고 N 줄 에 서 는 N 종 컷 팅.
첫 번 째 숫자 C 는 이 절단 법 으로 과일 을 몇 개 썰 수 있 는 지 를 나타 낸다.
두 번 째 숫자 는 이런 절 법 이 처 한 시간 을 나타 낸다.
후 C 개의 숫자 는 이때 이런 절단 법 으로 자 른 과일 번 호 를 나타 낸다.
주의: 3 개 이상 을 동시에 잘라 야 연 격 을 표시 하 며, 과일 한 개 는 최대 한 번 만 썰 수 있 습 니 다.
사고: 직접 검색 하고 가 지 를 자 르 세 요.
 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;



int gap,n,m;

int vis[205];



int tans[35];//    ，      

int ans[35];

int tanstop;

int anstop;





struct node

{

    vector<int>num;

    int cnt;

    int time;

    int id;

    bool operator < (const node &cmp) const

    {

        return time<cmp.time;

    }

}cut[35];





void dfs(int ttime,int pos)

{

    if(m-pos+tanstop<=anstop) return;//              ANS ，         A*   

    for(int i=pos+1;i<=m;i++)

    {

        if(cut[i].time-ttime<=gap||!tanstop)//          。    ！tanstop   

        {

            int tot=0;

            int SIZE=cut[i].num.size();

            for(int j=0;j<SIZE;j++)

            {

                if(vis[cut[i].num[j]]==0)

                {

                    tot++;

                }

                vis[cut[i].num[j]]++;

            }

            if(tot>=3)

            {

                tans[tanstop++]=cut[i].id;

                dfs(cut[i].time,i);

                tanstop--;

            }

            for(int j=0;j<SIZE;j++)

                vis[cut[i].num[j]]--;

        }

        else break;//                     

    }

        if(tanstop>anstop)

        {

            anstop=0;

            for(int i=0;i<tanstop;i++)

            ans[anstop++]=tans[i];

        }

    

}



int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        tanstop=anstop=0;



        memset(vis,0,sizeof(vis));



        scanf("%d%d%d",&m,&n,&gap);



        for(int i=1;i<=m;i++)

        {

            cut[i].num.clear();

            scanf("%d%d",&cut[i].cnt,&cut[i].time);

            cut[i].id=i;

            for(int j=0;j<cut[i].cnt;j++)

            {

                int tmp;

                scanf("%d",&tmp);

                cut[i].num.push_back(tmp);

            }

            if(cut[i].cnt<=2){i--;m--;}

        }

        

        sort(cut+1,cut+m+1);//                DFS



        dfs(1,0);





        printf("%d
",anstop);



        sort(ans,ans+anstop);//      



        for(int i=0;i<anstop-1;i++)

        printf("%d ",ans[i]);

        printf("%d
",ans[anstop-1]);

    }

    return 0;

}