USACO 4.2.4 Cowcycles 奶牛自行車 cowcycle
本文正體字版由OpenCC轉換
這是一道搜索題，題意不難理解，註釋寫得很清楚了。數據不是很BT，寫個搜索，加些優化基本上就過了。似乎這道題同樣算法用C++寫比Pascal快得多。
搜索就是簡單的搜索組合，用兩個遞歸就可以了。
優化技巧：
- 最大傳動比率至少是最小的3倍。這個其實不用算出比率在判斷，只要不滿足s1[F]/s2[1]-s1[1]/s2[R]>=3的都剪掉(s1表示前齒輪型號，s2表示後齒輪型號)。另外乘法計算要比除法快得多，上面判斷式可以寫成s1[F]*s2[R]>=3*s1[1]*s2[1]。這個剪枝很有效果。
- 改變求方差的方法，
。用右面的式子代替原來的。 - 當找到比當前更優秀的解的時候，不要用For循環一個一個複製當前解，用memcpy函數會更快。
- 最想不到地地方，排序方法！開始我寫成快排，一直過不了。其實數據的數量太少的時候，用快排效率很低的。在這裏最適合的是簡單插入排序。這個剪枝的效率很驚人！
Compiling… Compile: OK
Executing… Test 1: TEST OK [0.011 secs, 1844 KB] Test 2: TEST OK [0.130 secs, 1848 KB] Test 3: TEST OK [0.108 secs, 1848 KB] Test 4: TEST OK [0.194 secs, 1848 KB] Test 5: TEST OK [0.421 secs, 1848 KB] Test 6: TEST OK [0.194 secs, 1844 KB] Test 7: TEST OK [0.443 secs, 1844 KB] Test 8: TEST OK [0.637 secs, 1844 KB]
All tests OK.
Your program (‘cowcycle’) produced all correct answers! This is your submission #2 for this problem. Congratulations!
/*
ID: cmykrgb1
PROG: cowcycle
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 11
using namespace std;
ifstream fi("cowcycle.in");
ofstream fo("cowcycle.out");
int s1[MAX],s2[MAX],ans1[MAX],ans2[MAX];
int F,R,F1,F2,R1,R2,cnt;
double rate[MAX*MAX],diff[MAX*MAX],minvf=0x7FFFFFFF;
void init()
{
fi >> F >> R >> F1 >> F2 >> R1 >> R2;
cnt=F*R;
}
void count()
{
int i,j,k=0,l;
double sum=0,avg,vf=0,sumf=0,p;
for (i=1;i<=F;i++)
for (j=1;j<=R;j++)
{
p=(double)s1[i]/s2[j];
l=++k;
while (rate[l-1]>=p)
{
rate[l]=rate[l-1];
l--;
}
rate[l]=p;
}
for (i=1;i<=cnt-1;i++)
{
diff[i]=rate[i+1]-rate[i];
sum+=diff[i];
sumf+=diff[i]*diff[i];
}
avg=sum/(cnt-1);
vf=sumf-sum*avg;
if (vf<minvf)
{
minvf=vf;
memcpy(ans1+1,s1+1,sizeof(int)*F);
memcpy(ans2+1,s2+1,sizeof(int)*R);
}
}
void sc2(int k,int w)
{
int i;
if (k==R+1)
{
if (s1[F]*s2[R]<3*s1[1]*s2[1])
return;
count();
return;
}
for (i=w;i<=(R2-(R-k));i++)
{
s2[k]=i;
sc2(k+1,i+1);
}
}
void sc1(int k,int w)
{
int i;
if (k==F+1)
{
sc2(1,R1);
return;
}
for (i=w;i<=(F2-(F-k));i++)
{
s1[k]=i;
sc1(k+1,i+1);
}
}
void print()
{
int i;
for(i=1;i<=F-1;i++)
fo << ans1[i] << ' ';
fo << ans1[F] << endl;
for(i=1;i<=R-1;i++)
fo << ans2[i] << ' ';
fo << ans2[R] << endl;
fi.close();
fo.close();
}
int main()
{
init();
sc1(1,F1);
print();
return 0;
}
上次修改時間 2017-02-03