Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:深度搜索,减枝后可达到0ms,贴代吗,请指教

Posted by 1000029 at 2015-07-20 01:20:15 on Problem 1010
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator