/*
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;
}

• 把dfs中最上面的判断由if(Sum>ans) 改为if(Sum>=ans) ，就由16MS变成了172MS (1350) a798253982 2013-07-30 09:56:02