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

请教``` 关于 半径的遍历顺序 出现剪枝错误```为什么?

Posted by __sunshine at 2009-08-06 19:52:34 on Problem 1190
#include <cstdlib>
#include <iostream>
#define inf 100000000
#define MAXN 22
using namespace std;

int N,ans,M,sem[MAXN],tem[MAXN];

inline int gets(int i){
       return (i*(i+1)*i*(i+1))/4;
}
inline int geta(int i){
       return (i*(i+1)*(2*i+1))/6;
}


void dfs(int num,int vum,int sum,int hlast,int rlast){
     
     if(num==0&&vum==0){
             ans=min(ans,sum);
             return ;
     }
     int t=tem[num-1];
     if(vum<tem[num-1] || sum+sem[num-1]>ans || 2*vum/(rlast)+sum>=ans) return ;   
                  
     for(int i=num;i<=rlast;i++){          //  这里 我 的 i  从 rlast 到     num  就会出现 剪掉正确答案``是怎么回事?  别人这么剪不也没错啊 
             int th=(vum-t)/(i*i);
             th=th<hlast?th:hlast;
             for(int j=th;j>=num;j--){
                      if(t==0&&i*i*j!=vum)continue;
                      if (2 * (vum - i * i * j) / i + sum + 2 * i * j >= ans) continue;

                     if(num==M)sum=i*i;
                     
                     dfs(num-1,vum-i*i*j,sum+2*i*j,j-1,i-1);
             }
     }
}
                     


int main(int argc, char *argv[])
{
     
     scanf("%d%d",&N,&M);
     ans=inf;
     fill(sem,sem+MAXN,inf);
     tem[0]=0;
     sem[0]=0;
     for(int i=1;i<=20;i++){
		     tem[i]=tem[i-1]+i*i*i;
		     sem[i]=sem[i-1]+2*i*i;
	}

     
     dfs(M,N,0,N-1,N-1);
    
     if(ans!=inf)printf("%d\n",ans);
     else printf("0\n");
                     
                     
    
    //system("PAUSE");
    return EXIT_SUCCESS;
}

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