結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2020-01-29 15:28:54 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 59 ms / 5,000 ms |
コード長 | 1,933 bytes |
コンパイル時間 | 3,433 ms |
コンパイル使用メモリ | 77,900 KB |
実行使用メモリ | 38,180 KB |
最終ジャッジ日時 | 2024-09-16 01:01:53 |
合計ジャッジ時間 | 5,745 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
import java.util.*; import java.io.*; public class Main { static int n; static int[] toys; static int m; static int[] boxes; static final int MAX = 20; static int[][][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); toys = new int[n]; String[] first = br.readLine().split(" ", n); for (int i = 0; i < n; i++) { toys[i] = Integer.parseInt(first[i]); } m = Integer.parseInt(br.readLine()); boxes = new int[m]; String[] second = br.readLine().split(" ", m); for (int i = 0; i < m; i++) { boxes[i] = Integer.parseInt(second[i]); } Arrays.sort(boxes); dp = new int[m][MAX + 1][1 << n]; int value = dfw(m - 1, boxes[m - 1], (1 << n) - 1) + 1; if (value > m) { System.out.println(-1); } else { System.out.println(value); } } static int dfw(int b, int size, int key) { if (b < 0) { return Integer.MAX_VALUE / 10; } if (key == 0) { return 0; } if (dp[b][size][key] != 0) { return dp[b][size][key]; } int min = Integer.MAX_VALUE; int count = 0; for (int i = 0; i < n; i++) { int x = 1 << i; if ((x & key) == 0) { continue; } if (toys[i] > size) { continue; } count++; min = Math.min(min, dfw(b, size - toys[i], key ^ x)); } if (count == 0) { if (b < 1) { return Integer.MAX_VALUE / 10; } min = dfw(b - 1, boxes[b - 1], key) + 1; } dp[b][size][key] = min; return min; } }