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

把dfs中最上面的判断由if(Sum>ans) 改为if(Sum>=ans) ,就由16MS变成了172MS

Posted by a798253982 at 2013-07-30 09:56:02 on Problem 2531
In Reply To:终于剪枝到16MS了。。 Posted by:a798253982 at 2013-07-30 09:48:52
> /*
> 1.等价剪枝:根据对称性剪枝
> 2.无法达最优:提前剪枝 
> 3.换个角度,更高效搜索算法 :如本题逆向思维求最小内部代价 
> */
> 
> #include <cstdio>
> #include <cstring>
> 
> int M[20][20],n,ans,arr1[20],arr2[20];
> 
> void dfs(int Sum,int p1,int p2,int cur)
> {
> 	if(Sum>=ans) 
> 		return;
> 	else if(cur==20)
> 		ans=Sum;
> 	else
> 	{
> 	    int sum,temp,temp1,temp2;
> 		
> 	    sum=0;
> 	    for(int i=0;i<p1;i++)
> 	    sum+=M[arr1[i]][cur];
> 	    temp1=arr1[p1];
>             arr1[p1]=cur;
> 	    dfs(Sum+sum,p1+1,p2,cur+1);
> 	    arr1[p1]=temp1;
> 	    
> 	    sum=0;
> 	    for(int i=0;i<p2;i++)
> 	    sum+=M[arr2[i]][cur];
> 	    temp2=arr2[p2];
> 	    arr2[p2]=cur;
> 	    dfs(Sum+sum,p1,p2+1,cur+1);
> 	    arr2[p2]=temp2;
> 	}
> }
> 
> int main(){
> 	int i,j,ans1,ans2,total=0;
> 	while(~scanf("%d",&n))
> 	{
> 		for(i=0;i<n;i++)
> 		    for(j=0;j<n;j++){
> 		        scanf("%d",&M[i][j]);total+=M[i][j];
> 		    }
> 		    
> 		ans1=0;
> 		for(i=0;i<n/2;i++)
> 			for(j=0;j<n/2;j++)
> 				ans1+=M[i][j];
> 		ans1/=2;
> 		
> 		ans2=0;
> 		for(i=n/2;i<n;i++)
> 		    for(j=n/2;j<n;j++)
> 		        ans2+=M[i][j];
> 		ans2/=2;
> 		        
> 		memset(arr1,0,sizeof(arr1));
> 		memset(arr2,0,sizeof(arr2));
> 		arr1[0]=0;
> 		ans=ans1+ans2;
> 		dfs(0,1,0,1);
> 		printf("%d\n",total/2-ans);
> 	}
> 	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