| ||||||||||
| 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