题目大意：题目就是描述的水果忍者。
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\n",anstop); sort(ans,ans+anstop);//要求升序输出 for(int i=0;i<anstop-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[anstop-1]);
}
return 0;
}