随笔-72  评论-126  文章-0  trackbacks-0



不同时刻提交不限不同的结果。。。。学习了。哈哈
比赛时候是在没有办法的时候又多了一招
付代码
#include "stdio.h"
#include 
"algorithm"
#include 
"time.h"
using namespace std;
int n,hash[25];
int A[25][25];
int res,maxdeep;
void fun() {
    
int sum = 0;
    
int a[25],b[25],la =0,lb =0;
    
for(int i =0 ; i < n ; i ++) {
        
if(hash[i])    a[la++= i;
        
else    b[lb++= i;
    }
    
for(int i = 0; i < la; i ++) {
        
for(int j =0 ; j < lb; j ++) {
            sum 
+= A[a[i]][b[j]];
        }
    }    
    
if(sum > res)    res = sum;
}
void dfs(int deep,int start) {
    
if(deep == maxdeep) {
        fun();
        
return ;
    }
    
for(int i =start; i < n ; i ++) {
        
if(!hash[i]) {
            hash[i] 
^= 1;
            dfs(deep
+1,i+1);
            hash[i] 
^= 1;
        }
    }
}
int main() {
    
int i,j;
    
while(scanf("%d",&n) == 1) {
        
for(i =0 ; i < n ; i ++) {
            
for(j =0 ; j < n ; j ++) {
                scanf(
"%d",&A[i][j]);
            }
        }
        res 
= 0;
        
if(n <= 19) {
            maxdeep 
= n / 2;
            memset(hash,
0,sizeof(hash));
            
while(maxdeep) {
                dfs(
0,0);
                maxdeep 
--;
            }
        } 
else {
            
int cnt = 100000;
            srand(time(NULL));
            memset(hash,
0,sizeof(hash));
            
while(cnt --) {
                hash[rand()
%n] ^= 1;
                fun();
            }
        }
        printf(
"%d.\n",res);
    }
    
return 0;
}

posted on 2009-05-15 10:01 shǎ崽 阅读(942) 评论(4)  编辑 收藏 引用

评论:
# re: 又学了一招,随机化法,用于比赛时候是在没办法的时候的流氓剪枝 2009-05-16 18:39 | yiflying
那是要罚时的呀比赛的时候  回复  更多评论
  
# re: 又学了一招,随机化法,用于比赛时候是在没办法的时候的流氓剪枝 2011-02-10 13:41 | hhh
@yiflying
多做出一道应该比罚多久都合算吧。。  回复  更多评论
  
# re: 又学了一招,随机化法,用于比赛时候是在没办法的时候的流氓剪枝 2011-05-09 21:09 | songl
具体怎么做呢 我一点都没看出流氓性质来啊  回复  更多评论
  
# re: 又学了一招,随机化法,用于比赛时候是在没办法的时候的流氓剪枝[未登录] 2011-08-18 20:01 | ...
hah   回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理