第一次用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