随笔-141  评论-9  文章-3  trackbacks-0

参考了USACO上的提示:

1. 最大传动比率至少是最小的3倍。这个其实不用算出比率再判断,只要不满足s1[F]/s2[1]-s1[1]/s2[R]>=3的都剪掉 .

2. 用memcpy函数会更快.

3. 用插入排序对于规模较小的数据速度比较客观.

/*
ID: lorelei3
TASK: cowcycle
LANG: C++
*/


#include 
<fstream>
#include 
<memory.h>

using namespace std;

const int MAX = 100;

int F, R, F1, F2, R1, R2;
int s1[MAX], s2[MAX];
int ans1[MAX], ans2[MAX];
double rate[MAX*MAX], diff[MAX*MAX];
double minf = 0x7FFFFFFF;

void count(){
    
int i,j,k=0;
    
double sum1=0, sum2=0, t=0;

    
for(i=1; i<=F; ++i)
        
for(j=1; j<=R; ++j){
            t 
= (double)s1[i]/s2[j];
            
int p=++k;
            
while(rate[p-1]>=t){
                rate[p] 
= rate[p-1];
                p
--;
            }

            rate[p] 
= t;
        }


    
int cnt = F*R;
    
for(i=1; i<=cnt-1++i){
        diff[i] 
= rate[i+1- rate[i];
        sum1 
+= diff[i];
    }


    
double mean = sum1/(cnt-1);

    
for(i=1; i<=cnt-1++i)
        sum2
+=(diff[i]-mean)*(diff[i]-mean);

    
double var = sum2/cnt-1;

    
if(var<minf){
        minf 
= var;
        memcpy(ans1
+1, s1+1sizeof(int)*F);
        memcpy(ans2
+1, s2+1sizeof(int)*R);
    }

}


void dfs2(int k, int w){
    
if(k==R+1){
        
if(s1[F]*s2[R]<3*(s1[1]*s2[1]) )
            
return;
        count();
        
return;
    }
else{
        
for(int i=w; i<=R2-(R-k); ++i){
            s2[k]
=i;
            dfs2(k
+1, i+1);
        }

    }

}


void dfs1(int k, int w){
    
if(k==F+1){
        dfs2(
1, R1);
        
return;
    }
else{
        
for(int i=w; i<=F2-(F-k); ++i){
            s1[k]
=i;
            dfs1(k
+1, i+1);
        }

    }

}


int main(){

    ifstream fin(
"cowcycle.in");
    ofstream fout(
"cowcycle.out");

    fin
>>F>>R>>F1>>F2>>R1>>R2;

    dfs1(
1,F1);

    
int i;
    
for(i=1; i<=F-1++i)
        fout
<<ans1[i]<<" ";
    fout
<<ans1[F]<<endl;

    
for(i=1; i<=R-1++i)
        fout
<<ans2[i]<<" ";
    fout
<<ans2[R]<<endl;

    
return 0;
}
posted on 2011-01-26 12:03 小阮 阅读(244) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理