Fence Rails

一道感觉很不错的搜索+剪枝的题目，当然剪枝策略我是参考来的，我自己想到的都是小剪枝

然后我自己用Java实现了，结果发现……，这速度啊，真让我郁闷，居然在第四个点就超时了

但是同样的算法用C++实现的代码，快了100+倍。

难怪现在还有这么多人在搞C++，也难怪有人批评说Java速度慢，还有些人在反驳

事实却是如此啊。

代码贴一下吧，TLE的，如果有人愿意的话，可以转成C++用就行了

其实我是想能不能再改进改进，让它用Java也能过，但是感觉很难，我已经想不出更好的剪枝的办法了

或者另外一个方法就是空间换时间，但是感觉已经没什么好换的了，该开的数组都开了。

 1 import java.io.*;
 2 import java.util.*;
 3 /*
 4 ID: yanglei4
 5 LANG: JAVA
 6 TASK:fence8
 7 */
 8 public class fence8{
 9     int wastemax = 0;
10     int ans;
11     int N,R;
12     int[] remain;
13     int[] rails;
14     int[] from = new int[1100];
15     PrintWriter out;
16     
17     public void dfs(int k, int waste) {
18         if (k < 0) {
19             out.println(ans + 1);
20             out.close();
21             System.exit(0);            
22         }
23         int i;
24         if(k != ans && rails[k] == rails[k + 1]) i = from[k + 1]; 
25         else i = 0;
26         
27         for (i = 0; i < N; i++) {
28             if (remain[i] >= rails[k]) {
29                 
30                 from[k] = i;
31                 remain[i] -= rails[k];
32                 if (remain[i] < rails[0]) waste += remain[i];
33                 if (waste > wastemax) {
34                     waste -= remain[i];
35                     remain[i] += rails[k];
36                     continue;
37                 }
38                 dfs(k - 1, waste);
39                 remain[i] += rails[k];
40             }
41         }
42     }
43     
44     public void done() throws IOException {
45         BufferedReader f = new BufferedReader(new FileReader("fence8.in"));
46         out = new PrintWriter(new BufferedWriter(new FileWriter("fence8.out")));
47         //Read the boards
48         N = Integer.parseInt(f.readLine());
49         int[] boards = new int[N];
50         int boardSum = 0;
51         for (int i = 0; i < N; i++) 
52             {
53                 boards[i] = Integer.parseInt(f.readLine());
54                 boardSum += boards[i];
55             }
56         Arrays.sort(boards);
57         
58         remain = new int[N];
59         for (int i = N - 1; i >= 0; i--) remain[i] = boards[i];
60         
61         // Read the rails
62         R = Integer.parseInt(f.readLine());
63         rails = new int[R];
64         int railSum = 0;
65         for (int i = 0; i < R; i++)
66             rails[i] = Integer.parseInt(f.readLine());        
67         Arrays.sort(rails);
68         
69         int i;
70         for (i = 0; i < R; i++) {
71             if (railSum + rails[i] > boardSum) 
72                 break;
73             railSum += rails[i];
74         }
75         int k = i - 1;
76         //Try every possible number
77         for (i = k; k >= 0; i--) {
78             ans = i;
79             wastemax = boardSum - railSum;
80             railSum -= rails[i];
81             dfs(i,0);
82         }
83         out.println(0);
84         out.close();    
85     }
86     public static void main(String[] args) throws IOException {
87         fence8 t = new fence8();
88         t.done();
89         System.exit(0);
90     }
91 }
92