HDU 4620 Fruit Ninja Extreme 暴搜

题目大意：题目就是描述的水果忍者。

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