結果
問題 | No.422 文字列変更 (Hard) |
ユーザー | hermione17 |
提出日時 | 2016-09-09 23:53:30 |
言語 | Java21 (openjdk 21) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,489 bytes |
コンパイル時間 | 3,184 ms |
コンパイル使用メモリ | 77,792 KB |
実行使用メモリ | 570,652 KB |
最終ジャッジ日時 | 2024-04-28 14:11:54 |
合計ジャッジ時間 | 31,464 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 100 ms
40,176 KB |
testcase_01 | AC | 1,737 ms
345,112 KB |
testcase_02 | AC | 2,200 ms
418,748 KB |
testcase_03 | AC | 1,633 ms
336,604 KB |
testcase_04 | AC | 1,696 ms
345,204 KB |
testcase_05 | AC | 2,214 ms
423,736 KB |
testcase_06 | MLE | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 2,334 ms
453,316 KB |
testcase_10 | AC | 2,402 ms
488,516 KB |
testcase_11 | AC | 1,767 ms
346,892 KB |
testcase_12 | AC | 1,618 ms
334,652 KB |
testcase_13 | AC | 1,556 ms
340,116 KB |
testcase_14 | AC | 1,690 ms
343,940 KB |
testcase_15 | AC | 1,728 ms
343,296 KB |
testcase_16 | AC | 1,739 ms
346,724 KB |
ソースコード
import java.io.BufferedOutputStream; import java.io.IOException; import java.io.OutputStream; import java.util.Scanner; public class Y422 { Y422() throws IOException { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); char[] S = sc.next().toCharArray(); char[] T = sc.next().toCharArray(); int[][][][] dp = new int[n+1][m+1][2][2]; int[][][][][] from = new int[n+1][m+1][2][2][]; for (int i = 0; i <= S.length; i++) { for (int j = 0; j <= T.length; j++) { for (int a = 0; a < 2; a ++) { for (int b = 0; b < 2; b ++ ) { dp[i][j][a][b] = 100 * (n + m); } } } } dp[0][0][0][0] = 0; for (int i = 0; i < S.length; i++) { for (int j = 0; j < T.length; j++) { int change_cost = 5; if (S[i] == T[j]) change_cost = 0; int cost = change_cost + dp[i][j][0][0]; { int[] tmp = { i, j, 0, 0 }; dp[i+1][j+1][0][0] = cost; from[i+1][j+1][0][0] = tmp; } cost = change_cost + dp[i][j][0][1]; if (cost < dp[i+1][j+1][0][0]) { int[] tmp = { i, j, 0, 1 }; dp[i+1][j+1][0][0] = cost; from[i+1][j+1][0][0] = tmp; } cost = change_cost + dp[i][j][1][0]; if (cost < dp[i+1][j+1][0][0]) { int[] tmp = { i, j, 1, 0 }; dp[i+1][j+1][0][0] = cost; from[i+1][j+1][0][0] = tmp; } cost = 9 + dp[i+1][j][0][0]; { int[] tmp = { i+1, j, 0, 0 }; dp[i+1][j+1][1][0] = cost; from[i+1][j+1][1][0] = tmp; } cost = 2 + dp[i+1][j][1][0]; if (cost < dp[i+1][j+1][1][0]) { int[] tmp = { i+1, j, 1, 0 }; dp[i+1][j+1][1][0] = cost; from[i+1][j+1][1][0] = tmp; } cost = 9 + dp[i+1][j][0][1]; if (cost < dp[i+1][j+1][1][0]) { int[] tmp = { i+1, j, 0, 1 }; dp[i+1][j+1][1][0] = cost; from[i+1][j+1][1][0] = tmp; } cost = 9 + dp[i][j+1][0][0]; { int[] tmp = { i, j+1, 0, 0 }; dp[i+1][j+1][0][1] = cost; from[i+1][j+1][0][1] = tmp; } cost = 9 + dp[i][j+1][1][0]; if (cost < dp[i+1][j+1][0][1]) { int[] tmp = { i, j+1, 1, 0 }; dp[i+1][j+1][0][1] = cost; from[i+1][j+1][0][1] = tmp; } cost = 2 + dp[i][j+1][0][1]; if (cost < dp[i+1][j+1][0][1]) { int[] tmp = { i, j+1, 0, 1 }; dp[i+1][j+1][0][1] = cost; from[i+1][j+1][0][1] = tmp; } } } int cost = 100 * (n + m); int[] state = null; for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { if (cost > dp[S.length][T.length][a][b]) { cost = dp[S.length][T.length][a][b]; int[] tmp = {S.length, T.length, a, b}; state = tmp; } } } char[] S_ans = new char[n+m]; char[] T_ans = new char[n+m]; int len = 0; while (state[0] != 0 || state[0] != 0) { int[] next = from[state[0]][state[1]][state[2]][state[3]]; if (state[2] == 1) { S_ans[len] = '-'; } else { S_ans[len] = S[next[0]]; } if (state[3] == 1) { T_ans[len] = '-'; } else { T_ans[len] = T[next[1]]; } len++; state = next; } OutputStream os = new BufferedOutputStream(System.out); os.write(Integer.toString(cost).getBytes()); os.write('\n'); for (int i = len - 1; i >= 0; i--) { os.write(S_ans[i]); } os.write('\n'); for (int i = len - 1; i >= 0; i--) { os.write(T_ans[i]); } os.write('\n'); os.flush(); } public static void main(String argv[]) throws IOException { new Y422(); } }