Fence Rails

一道感覺很不錯的搜索+剪枝的題目，當然剪枝策略我是參考來的，我自己想到的都是小剪枝

然后我自己用Java實現(xiàn)了，結果發(fā)現(xiàn)……，這速度啊，真讓我郁悶，居然在第四個點就超時了

但是同樣的算法用C++實現(xiàn)的代碼，快了100+倍。

難怪現(xiàn)在還有這么多人在搞C++，也難怪有人批評說Java速度慢，還有些人在反駁

事實卻是如此啊。

代碼貼一下吧，TLE的，如果有人愿意的話，可以轉成C++用就行了

其實我是想能不能再改進改進，讓它用Java也能過，但是感覺很難，我已經(jīng)想不出更好的剪枝的辦法了

或者另外一個方法就是空間換時間，但是感覺已經(jīng)沒什么好換的了，該開的數(shù)組都開了。

 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