結果
問題 | No.247 線形計画問題もどき |
ユーザー |
|
提出日時 | 2015-07-15 17:07:37 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 996 bytes |
コンパイル時間 | 3,451 ms |
コンパイル使用メモリ | 77,512 KB |
実行使用メモリ | 42,036 KB |
最終ジャッジ日時 | 2024-07-07 10:59:13 |
合計ジャッジ時間 | 7,056 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Yuki_678 { public Yuki_678() { Scanner scanner = new Scanner(System.in); int A = scanner.nextInt(); int N = scanner.nextInt(); int[] data = new int[N]; for (int i = 0; i < N; i++) { data[i] = scanner.nextInt(); } int[] dp = new int[100000 + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 0; i <= A; i++) { for (int j = 0; j < N; j++) { int k = i - data[j]; if (k >= 0 && dp[k] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[k] + 1); } } } if (dp[A] == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(dp[A]); } } public static void main(String[] args) { Yuki_678 hoge = new Yuki_678(); } }