HDU 4620 Fruit Ninja Extreme Search dfs

 

is dfs branch will be able to add a few less than one start dfs stack which causes the program to open the vector into an array like a giant slow search for time cards or caution STL tight right

 

  

#include <string> 
#include <cstring> 
#include <algorithm> 
#include <cstdio> 
#include <iostream> 
#include <cmath> 
#include <queue> 
#include <vector> 
#include <set> 
#include <stack> 
#include <map> 
#define maxn 320 
#define maxe 10000*8 
#define inf 1000000000 
#define eps 1e-9 
using namespace std; 
 
struct node 
{ 
    int ti,id; 
    int num; 
    int tar[12]; 
    void input() 
    { 
        int i; 
        scanf("%d %d",&num,&ti); 
        for(i=0; i<num; i++) 
        { 
            scanf("%d",&tar[i]); 
        } 
    } 
    bool operator<(const node& rhs)const 
    { 
        return ti<rhs.ti; 
    } 
} p[50]; 
int N,M,W; 
bool vis[maxn]; 
int temp[40],ans[40]; 
int sum; 
int ts,as; 
 
void dfs(int cur,int pti) 
{ 
    int i,j; 
    if(ts>as) 
    { 
        copy(temp,temp+ts,ans); 
        as=ts; 
    } 
    if(cur>=N) 
    { 
        return; 
    } 
    if(ts+N-cur<=as) 
    { 
        return; 
    } 
    if(M-sum<3) 
    { 
        return ; 
    } 
 
    for(i=cur; i<N; i++) 
    { 
        if((p[i].ti-pti>W)&&(pti!=-1)) 
        { 
            break; 
        } 
 
        if(p[i].num<3) continue; 
        int tt[20]; 
        int cnt = 0; 
        for(j=0;j<p[i].num;j++) 
        { 
            if(!vis[p[i].tar[j]]) 
            { 
                tt[cnt++] = p[i].tar[j]; 
            } 
        } 
        if( cnt < 3 ) continue; 
 
        for(j=0;j<cnt;j++) 
        { 
            vis[tt[j]]=1; 
        } 
        temp[ts++]=p[i].id; 
        sum+=cnt; 
 
        dfs(i+1,p[i].ti); 
 
        sum-=cnt; 
        ts--; 
        for(j=0;j<cnt;j++) 
        { 
            vis[tt[j]]=0; 
        } 
    } 
} 
 
int main() 
{ 
    //freopen("input.txt","r",stdin); 
    int i; 
    int T; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d %d %d",&N,&M,&W); 
        for(i=0; i<N; i++) 
        { 
            p[i].id=i; 
            p[i].input(); 
        } 
        sort(p,p+N); 
        memset(vis,0,sizeof(vis)); 
        ts=as=0; 
        sum=0; 
        dfs(0,-1); 
        sort(ans,ans+as); 
        printf("%d\n",as); 
        for(i=0; i<as; i++) 
        { 
            printf("%d",ans[i]+1); 
            if(i==as-1) 
            { 
                puts(""); 
            } 
            else 
            { 
                printf(" "); 
            } 
        } 
    } 
    return 0; 
}