Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:深度搜索,减枝后可达到0ms,贴代吗,请指教In Reply To:深度搜索,减枝后可达到0ms,贴代吗,请指教 Posted by:1064232633 at 2015-06-26 20:04:50 > #include<stdio.h> > #include<string.h> > #include<algorithm> > using namespace std; > > typedef struct{ > int index,value; > }Item; > > bool istie = false; > int a[66],n,ltype,lstamp,lsh; > Item id[4],lim[4]; > > int generatePermutation(int total,int cur){ > int s = 0; > for(int i = 0;i<cur;i++) s+=id[i].value; > if(s>total) return 1; > else if(s==total){ > int cstamp = cur,ctype = cur; > for(int i = 0;i<cur-1;i++) > if(id[i].index==id[i+1].index) ctype--; > if(ctype>ltype || (ctype==ltype && cstamp<lstamp) || (ctype==ltype && cstamp==lstamp && id[cur-1].value>lsh)){ > ltype = ctype; > lstamp = cstamp; > lsh = id[cur-1].value; > memcpy(lim,id,sizeof(Item)*cur); > istie = false; > }else if(ctype==ltype && cstamp==lstamp && id[cur-1].value==lsh){ > istie = true; > } > return 0; > }else if(cur<4){ > for(int i = (cur>0?id[cur-1].index:0);i<n;i++){ > id[cur].index = i; > id[cur].value = a[i]; > if(generatePermutation(total,cur + 1)) break; > } > } > return 0; > } > > int main() > { > while(scanf("%d",&a[n=0])!=EOF){ > int b,i = 0,j=1,lx = 1; > while(scanf("%d",&a[++n]) && a[n]); > sort(a,a+n); > while(j<n){ > if(a[i]==a[j]) lx++; > else lx = 1; > if(lx>5){ > while(j<n && a[i]==a[++j]); > if(j==n) break; > else lx = 1; > } > a[++i] = a[j++]; > } > n = i + 1; > > while(scanf("%d",&b) && b){ > ltype = lstamp = lsh = 0; > istie = false; > memset(id,0,sizeof(id)); > generatePermutation(b,0); > if(istie) printf("%d (%d): tie\n",b,ltype); > else if(!ltype) printf("%d ---- none\n",b); > else{ > printf("%d (%d):",b,ltype); > for(int j = 0;j<lstamp;j++) > printf(" %d",lim[j].value); > printf("\n"); > } > > } > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator