結果
問題 | No.266 最終進化を目指せ |
ユーザー |
|
提出日時 | 2015-08-06 17:32:40 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 1,301 bytes |
コンパイル時間 | 2,973 ms |
コンパイル使用メモリ | 78,088 KB |
実行使用メモリ | 41,744 KB |
最終ジャッジ日時 | 2024-07-18 03:39:48 |
合計ジャッジ時間 | 7,034 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import java.util.Scanner; public class Yuki_596 { public Yuki_596() { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] S = new int[N + 1]; for (int i = 0; i <= N; i++) { S[i] = scanner.nextInt(); } int T = S[S.length - 1] + 1; int[][] dp = new int[N + 1][T]; for (int i = 1; i <= N; i++) { dp[i][0] = i + 1; } for (int i = 0; i <= S[0]; i++) { dp[0][i] = i + 1; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= T; j++) { if (j > S[i]) { continue; } dp[i][j] = dp[i][0] + dp[i][j - 1]; for (int k = 0; k < j; k++) { dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[i][j - k - 1]); } if (dp[i - 1][j] > 0) { dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1); } } } for (int i = 0; i < T; i++) { if (i >= 1) { System.out.print(" "); } System.out.print(dp[N][i]); } } public static void main(String[] args) { Yuki_596 hoge = new Yuki_596(); } }