結果
問題 |
No.247 線形計画問題もどき
|
ユーザー |
|
提出日時 | 2015-07-17 23:32:49 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 278 ms / 2,000 ms |
コード長 | 1,155 bytes |
コンパイル時間 | 3,004 ms |
コンパイル使用メモリ | 77,492 KB |
実行使用メモリ | 102,068 KB |
最終ジャッジ日時 | 2024-07-07 11:02:57 |
合計ジャッジ時間 | 8,313 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
import java.util.Arrays; import java.util.Scanner; public class Main_yukicoder247 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int c = sc.nextInt(); int n = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } final int INF = Integer.MAX_VALUE / 2; int[][] dp = new int[n + 1][c + 1]; for (int i = 0; i <= n; i++) { Arrays.fill(dp[i], INF); } for (int i = 1; i <= n; i++) { dp[i][0] = 0; for (int j = 1; j <= c; j++) { dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]); if (j >= a[i - 1]) { dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - a[i - 1]] + 1); dp[i][j] = Math.min(dp[i][j], dp[i][j - a[i - 1]] + 1); } } } int min = INF; for (int i = 1; i <= n; i++) { min = Math.min(min, dp[i][c]); } if (min == INF) { System.out.println(-1); } else { System.out.println(min); } sc.close(); } }