题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4620

题目大意：

切水果。给n刀，每刀的时间，每刀切的水果的种类。求能切的最多的刀数，使得每相邻的两刀时间差不超过给定的w.前面切了的水果不能再切，每刀至少要切不少于三个的新的水果。

解题思路：

直接一个一个的暴搜的话会超时。

这里从每相邻两刀时间间隔不能超过w来考虑剪枝。问题抽象出来就是从给定的刀中选，相邻的选的话，不如按时间排序从小到大选，这样的效果更好，而且还可以剪枝。

本题排序剪枝很关键。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

//freopen("data.in","r",stdin);

//freopen("data.out","w",stdout);

int hav[220]; //hav[i]表示已经切了的水果i

int ti[35],num[35],fru[35][12],pos[35];

int n,m,w;

struct Node

{

   int sa[35];

   int cnt;

}ans,temp;

//对时间进行排序后，可以大大剪枝。

void dfs(int cur)

{

   if(temp.cnt>ans.cnt)

      ans=temp;

   if(n-cur+temp.cnt<=ans.cnt)//这个剪枝很关键

      return ;

   for(int i=cur+1;i<=n;i++) //排序后可以剪枝

   {

      int pp=pos[i];

      int aa[12];

      if(temp.cnt&&ti[pp]-ti[pos[cur]]>w) //如果前面至少选了一个

         break;

      int sum=0; //前面一个都没选的话，任何一个都可以作为第一个

      for(int j=1;j<=num[pp];j++)

      {

         aa[j]=hav[fru[pp][j]];

         if(!aa[j])

            sum++;

      }

      if(sum<3)

         continue;

      for(int j=1;j<=num[pp];j++)

         hav[fru[pp][j]]|=1;

      temp.sa[++temp.cnt]=pp;

      dfs(i);

      temp.cnt--;

      for(int j=1;j<=num[pp];j++)

         hav[fru[pp][j]]=aa[j];

   }

}

bool cmp(int a,int b)

{

   return ti[a]<ti[b];

}

int main()

{

   int t;

   scanf("%d",&t);

   while(t--)

   {

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

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

      {

         scanf("%d%d",&num[i],&ti[i]);

         for(int j=1;j<=num[i];j++)

            scanf("%d",&fru[i][j]);

         pos[i]=i;

      }

      sort(pos+1,pos+n+1,cmp); //对时间进行排序

      ans.cnt=0,temp.cnt=0;

      memset(hav,0,sizeof(hav));

      dfs(0);

      printf("%d\n",ans.cnt);

      sort(ans.sa+1,ans.sa+ans.cnt+1);//输出按升序来

      if(!ans.cnt)

         continue;

      printf("%d",ans.sa[1]);

      for(int i=2;i<=ans.cnt;i++)

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

      putchar('\n');

   }

   return 0;

}