結果
問題 | No.225 文字列変更(medium) |
ユーザー |
![]() |
提出日時 | 2016-10-25 22:53:56 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 58 ms / 5,000 ms |
コード長 | 1,732 bytes |
コンパイル時間 | 1,354 ms |
コンパイル使用メモリ | 107,904 KB |
実行使用メモリ | 20,608 KB |
最終ジャッジ日時 | 2024-12-24 13:05:41 |
合計ジャッジ時間 | 3,043 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.IO;using System.Collections;using System.Collections.Generic;using System.Text;using System.Linq;class Template{static Scanner sc;public static void Main(string[] args){sc = new Scanner();var nm = sc.nextIntArray();int n = nm[0], m = nm[1];string S = sc.next();string T = sc.next();int[,] dp = new int[n + 1, m + 1];for (int i = 0; i <= n; i++){for (int j = 0; j <= m; j++){dp[i, j] = (int)1e9;}}//dp[i, j] : Sのi文字目までと,Tのj文字目までのレーベンシュタイン距離for (int i = 0; i <= n; i++){dp[i, 0] = i;}for (int i = 0; i <= m; i++){dp[0, i] = i;}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (S[i - 1] != T[j - 1]){dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j - 1] + 1);}else{dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j - 1]);}dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j] + 1);dp[i, j] = Math.Min(dp[i, j], dp[i, j - 1] + 1);}}Console.WriteLine(dp[n, m]);}}public class Scanner{public Scanner() { }public string next(){return Console.ReadLine();}public int nextInt(){return int.Parse(next());}public double nextDouble(){return double.Parse(next());}public long nextLong(){return long.Parse(next());}public string[] nextArray(){return next().Split(' ');}public int[] nextIntArray(){return Array.ConvertAll(nextArray(), e => int.Parse(e));}public long[] nextLongArray(){return Array.ConvertAll(nextArray(), e => long.Parse(e));}public double[] nextDoubleArray(){return Array.ConvertAll(nextArray(), e => double.Parse(e));}}