参考了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+1, sizeof(int)*F);
memcpy(ans2+1, s2+1, sizeof(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
小阮 阅读(256)
评论(0) 编辑 收藏 引用 所属分类:
USACO