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