第一次用Java代码过搜索+剪枝的题目啊,不容易啊……,而且还是参考了后面的Analysis,-_-!

不过里面的那个Hash的剪枝还是很强大的,再一次说明了学好数学的重要

同时,再一次证明了Java有多慢,C++肯定不用加最后的剪枝就过了,但是Java就不行

而且有一个点居然要1.5秒,真是不可思议。

待会儿我再试试Analysis里面的代码,看看有多快,是不是Static的要比正常的写快。

算法没啥好说的,就是生成,把F+R个数生成出来,然后用那个最大ratio是最小ratio的三倍做一个剪枝

我之前还打了一个表,所有的数的ratio的表,然后后面直接访问这个表,而不是去现去除

但是发现好像左右不大。

剩下的就是那个Hash的优化了,很强大,就好象题目里说的那样,就是看F生成好之后的比率

比如1 3 5 7,前两个是F的,后两个是R的,那么它的variance和2 6 10 14是一样的,这个不用我解释吧

这样的话呢,同一个比率的就不用再做第二次了。

自己没有去严格的证明这个剪枝的正确性,但是想想证明应该不太难。

同一个ratio的话肯定取前面那组,如果是不同的ratio呢?

现在的问题就是,如果是不同的ratio,后面的正确的组会不会被前面的不小心剪掉。或者后面的这组根本没必要。

如果是根本没必要的话,那么这个剪枝肯定就是正确的了。

其实这个剪枝是正确的,因为在你用比如1,3的时候,你就试过了后面所有的不同组合了。

那么当你扩大1,3到2,6时,我们可以看看USACO后面的解释的那个例子来。

39/16 = 2.43750000000000000000

40/16 = 2.50000000000000000000

39/15 = 2.60000000000000000000

40/15 = 2.66666666666666666666

39/14 = 2.78571428571428571428

40/14 = 2.85714285714285714285

39/13 = 3.00000000000000000000

40/13 = 3.07692307692307692307

39/12 = 3.25000000000000000000

40/12 = 3.33333333333333333333


就相当于这些ratio全都翻了一倍,那样的话,variance当然不会变

所以个剪枝是正确的。

贴一下代码:
  1 import java.io.*;
  2 import java.util.*;
  3 /*
  4 ID: yanglei4
  5 LANG: JAVA
  6 TASK:cowcycle
  7 */
  8 public class cowcycle{
  9     public double[][] ratio = new double[81][41];
 10     int F,R,F1,F2,R1,R2;
 11     public int[] s1;
 12     public int[] s2;
 13     double min = 1000000;
 14     static String[] hash;
 15     public int[] ans1;
 16     public int[] ans2;
 17     
 18     public static boolean contains(String str) {
 19         int num = str.hashCode();
 20         if(num<0) num = -num;
 21         int p = num % hash.length;
 22         while(hash[p]!=null)
 23             if(str.equals(hash[p]))   return true;
 24             else if(p==hash.length-1) p=0;
 25             else p++;
 26         hash[p]=str;
 27         return false;
 28    }
 29 
 30     public void DFS_F(int step,int start) {
 31         if (step == F + 1) {
 32             StringBuffer str = new StringBuffer();
 33             for(int i = 2;i <= F;i++)
 34                 str.append((int)(100*(double)s1[i]/s1[1]));
 35             if(contains(str.toString())) return;
 36             
 37             DFS_R(1,R1);
 38             return;
 39         }
 40         for (int i = start; i <= F2 - (F - step); i++) {
 41             s1[step] = i;
 42             DFS_F(step + 1, i + 1);
 43         }
 44     }
 45     
 46     public void DFS_R(int step,int start) {
 47         if (step == R + 1) {
 48             if (s1[F] * s2[R] < 3 * s1[1* s2[1])
 49                 return;
 50             count();
 51             return;
 52         }
 53         for (int i = start; i <= R2 - (R - step); i++) {
 54             s2[step] = i;
 55             DFS_R(step + 1, i + 1);
 56         }        
 57     }
 58     
 59     public double count() {
 60         double[] rate = new double[R * F + 1];
 61         double[] diff = new double[R * F + 1];
 62         double sum = 0;
 63         double sumf = 0;
 64         int l = 1;
 65         for (int i = 1; i <= F; i++)
 66             for (int j = 1; j <= R; j++
 67                 rate[l++= ratio[s1[i]][s2[j]];
 68 
 69         Arrays.sort(rate);
 70         
 71         for (int i = 1; i <= F * R - 1; i++) {
 72             diff[i] = rate[i + 1- rate[i];
 73             sum += diff[i];
 74             sumf += diff[i] * diff[i];
 75         }
 76         double avg = sum / (F * R - 1);
 77         double vf = sumf - sum * avg;
 78         if (vf < min) {
 79             min = vf;
 80             for (int i = 1; i <= F; i++) ans1[i] = s1[i];
 81             for (int i = 1; i <= R; i++) ans2[i] = s2[i];
 82         }
 83         return 0.0;
 84     }
 85     
 86     public void done() throws IOException {
 87         for (int i = 25; i <= 80; i++)
 88             for (int j = 5; j <= 40; j++
 89                 ratio[i][j] = (double)i / j;
 90 
 91         BufferedReader f = new BufferedReader(new FileReader("cowcycle.in"));
 92         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("cowcycle.out")));
 93         StringTokenizer st = new StringTokenizer(f.readLine());
 94         F = Integer.parseInt(st.nextToken());
 95         R = Integer.parseInt(st.nextToken());
 96         st = new StringTokenizer(f.readLine());
 97         F1 = Integer.parseInt(st.nextToken());
 98         F2 = Integer.parseInt(st.nextToken());
 99         R1 = Integer.parseInt(st.nextToken());
100         R2 = Integer.parseInt(st.nextToken());
101         s1 = new int[F + 1];
102         s2 = new int[R + 1];
103         ans1 = new int[F + 1];
104         ans2 = new int[R + 1];
105         hash = new String[50003];
106         
107         DFS_F(1,F1);
108         
109         for (int i = 1; i <= F - 1; i++)
110             out.print(ans1[i] + " ");
111         out.println(ans1[F]);
112 
113         for (int i = 1; i <= R - 1; i++)
114             out.print(ans2[i] + " ");
115         out.println(ans2[R]);
116                 
117         out.close();
118     }
119     
120     public static void main(String[] args) throws IOException {
121         cowcycle t = new cowcycle();
122         t.done();
123         System.exit(0);
124     }
125 }
126