SHOW:
|
|
- or go back to the newest paste.
| 1 | - | void gen(ArrayList<Integer> length, ArrayList<Integer> times) {
|
| 1 | + | |
| 2 | pow = new int[n + 1]; | |
| 3 | pow[0] = 1; | |
| 4 | for (int i = 1; i <= n; i++) | |
| 5 | pow[i] = 3 * pow[i - 1]; | |
| 6 | ArrayList<Integer> curArr = new ArrayList<Integer>(); | |
| 7 | for (int i = 0; i < n; i++) | |
| 8 | curArr.add(1 << n); | |
| 9 | time = new boolean[pow[n] * n + 1]; | |
| 10 | ArrayList<Integer> times = new ArrayList<Integer>(); | |
| 11 | times.add(0); | |
| 12 | time[0] = true; | |
| 13 | gen(curArr, times); | |
| 14 | ArrayList<Integer> ans = new ArrayList<Integer>(); | |
| 15 | for (int i = 0; i <= pow[n] * n; i++) | |
| 16 | if (time[i]) | |
| 17 | ans.add(i); | |
| 18 | for (int i = 0; i < ans.size() - 1; i++) | |
| 19 | out.print(ans.get(i) + ", "); | |
| 20 | out.print(ans.get(ans.size() - 1)); | |
| 21 | } | |
| 22 | ||
| 23 | void gen(ArrayList<Integer> length, ArrayList<Integer> times) {
| |
| 24 | if (length.size() == 0) {
| |
| 25 | for (int i = 0; i < times.size(); i++) {
| |
| 26 | for (int j = i + 1; j < times.size(); j++) | |
| 27 | time[times.get(j) - times.get(i)] = true; | |
| 28 | } | |
| 29 | return; | |
| 30 | } | |
| 31 | for (int mask = 1; mask < pow[length.size()]; mask++) {
| |
| 32 | int minTime = Integer.MAX_VALUE; | |
| 33 | - | } |
| 33 | + | |
| 34 | int maskI = (mask / pow[i]) % 3; | |
| 35 | if (maskI == 1) | |
| 36 | minTime = Math.min(minTime, length.get(i)); | |
| 37 | if (maskI == 2) | |
| 38 | minTime = Math.min(minTime, length.get(i) / 2); | |
| 39 | } | |
| 40 | ArrayList<Integer> newLength = new ArrayList<Integer>(); | |
| 41 | for (int i = 0; i < length.size(); i++) {
| |
| 42 | int maskI = (mask / pow[i]) % 3; | |
| 43 | int nextLen = length.get(i); | |
| 44 | if (maskI == 1) | |
| 45 | nextLen -= minTime; | |
| 46 | if (maskI == 2) | |
| 47 | nextLen -= 2 * minTime; | |
| 48 | if (nextLen != 0) | |
| 49 | newLength.add(nextLen); | |
| 50 | } | |
| 51 | times.add(times.get(times.size() - 1) + minTime); | |
| 52 | gen(newLength, times); | |
| 53 | times.remove(times.size() - 1); | |
| 54 | } | |
| 55 | } |
