結果
問題 | No.266 最終進化を目指せ |
ユーザー |
![]() |
提出日時 | 2015-08-07 23:36:02 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 1,271 bytes |
コンパイル時間 | 2,048 ms |
コンパイル使用メモリ | 77,344 KB |
実行使用メモリ | 54,488 KB |
最終ジャッジ日時 | 2024-07-18 05:25:14 |
合計ジャッジ時間 | 6,240 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
package no266;import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] s = new int[n+1];for(int i=0;i<=n;i++) {s[i] = sc.nextInt();}int[][] dp = new int[n+1][11];for(int i=0;i<=n;i++) {Arrays.fill(dp[i], 1 << 29);}dp[0][0] = 1;for(int i=0;i<=n;i++) {for(int j=0;j<=s[i];j++) {if (j > 0) {int[][] dp2 = new int[3][j];for(int k=0;k<3;k++) {Arrays.fill(dp2[k], 1 << 29);}dp2[0][0] = 0;dp2[1][0] = dp[i][0];dp2[2][0] = dp[i][0] * 2;for(int k=1;k<j;k++) {for(int l=0;l+k<j;l++) {for(int m=0;m<3;m++) {int m2 = Math.min(2, m+1);dp2[m2][l+k] = Math.min(dp2[m2][l+k], dp2[m][l] + dp[i][k]);}}}dp[i][j] = dp2[2][j-1];// System.out.println(i + "," + j + "," + Arrays.deepToString(dp2));}if (i > 0) {dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);}}}// System.out.println(Arrays.deepToString(dp));StringBuilder sb = new StringBuilder();for(int i=0;i<=s[n];i++) {if (i > 0) {sb.append(' ');}sb.append(dp[n][i]);}System.out.println(sb);}}