对t进行从小到大排序(要记录ID),然后直接dfs。
剪枝的话,利用A*的思想,假设之后的全部连击也不能得到更优解。
因为要回溯,而且由于每次cut 的数目不会超过10,所以需要回溯的下标可以利用一个二进制保存。
由于cut最多30个,所以方案也可以用一个二进制保存。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<stack> using namespace std; bool vis[205]; struct node { int t; int f[205]; int top; int id; }cut[205]; int n,m,w,ans; int p; int ansp; bool cmp(const node &a,const node &b) { return a.t<b.t; } void dfs(int now,int score) { if(n-now+score<=ans) return; for(int i=now+1;i<=n;i++) { int aa=0; if(cut[i].top<3) continue; if(cut[i].t-cut[now].t>w&&score) break; int tot=0; for(int j=1;j<=cut[i].top;j++) if(!vis[cut[i].f[j]]) vis[cut[i].f[j]]=1,aa|=(1<<(j-1)),tot++; if(tot>=3) { p|=(1<<(cut[i].id-1)); dfs(i,score+1); p&=(~(1<<(cut[i].id-1))); } int tt=1; while(aa) { if(aa&1) { vis[cut[i].f[tt]]=0; } aa>>=1; tt++; } } if(score>ans) { ans=score; ansp=p; } } int main() { int cas; scanf("%d",&cas); while(cas--) { scanf("%d%d%d",&n,&m,&w); for(int i=1;i<=n;i++) { scanf("%d%d",&cut[i].top,&cut[i].t); cut[i].id=i; for(int j=1;j<=cut[i].top;j++) scanf("%d",&cut[i].f[j]); } p=0; ans=0; memset(vis,false,sizeof(vis)); sort(cut+1,cut+n+1,cmp); dfs(0,0); printf("%d ",ans); int tt=1; while(ansp) { if(ansp&1) { if(tt==1) printf("%d",tt); else printf(" %d",tt); } ansp=(ansp>>1); tt++; } printf(" "); } }