SHOW:
|
|
- or go back to the newest paste.
| 1 | public class Coins {
| |
| 2 | - | public static int[] V = new int[] {1, 3, 5};
|
| 2 | + | public static int[] V; |
| 3 | - | public static int S = 11; |
| 3 | + | public static int S = 10000000; |
| 4 | static int asdf = 0; | |
| 5 | public static void main(String[] args) {
| |
| 6 | - | System.out.println(recurse(2, 0)); |
| 6 | + | V = new int[100]; |
| 7 | for (int i = 0; i < 100; ++i) | |
| 8 | {
| |
| 9 | V[i] = i * 2 + 1; | |
| 10 | } | |
| 11 | System.out.println(recurse(V.length - 1, 0)); | |
| 12 | System.out.println(asdf); | |
| 13 | - | for (int j = (S - total) / V[i]; j >= 0; j--) {
|
| 13 | + | |
| 14 | ||
| 15 | public static int recurse(int i, int total) {
| |
| 16 | int min = -1; | |
| 17 | int num = 0; | |
| 18 | if (i < 0) return (S - total == 0) ? 0 : -1; | |
| 19 | int N = (S - total) / V[i]; | |
| 20 | for (int j = N; j >= 0 && j >= N - 1; j--) {
| |
| 21 | int tmp = recurse(i - 1, total + V[i] * j); | |
| 22 | if (tmp >= 0 && (min == -1 || tmp < min)) {
| |
| 23 | min = tmp; | |
| 24 | num = j; | |
| 25 | } | |
| 26 | ++asdf; | |
| 27 | } | |
| 28 | return min + num; | |
| 29 | } | |
| 30 | } |