結果

問題 No.225 文字列変更(medium)
ユーザー IL_mstaIL_msta
提出日時 2015-06-13 19:01:52
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,847 bytes
コンパイル時間 709 ms
コンパイル使用メモリ 84,500 KB
実行使用メモリ 11,292 KB
最終ジャッジ日時 2024-07-06 19:50:44
合計ジャッジ時間 13,217 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

#include <algorithm>
#include <cmath>

#include <string>
#include <list>
#include <queue>
#include <vector>
#include <complex>

/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) std::cout<<(p)<<std::endl;
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////

int solve(string s, string t,int num,int Lcount,int N){
	//cout << s << " " << num << " " << Lcount << " " << N << endl;
	if(t.size() == num){
		return Lcount;
	}
	else if( Lcount >= N ){
		return -1;
	}

	int r = -1;
	for( int i=num; i< s.size() && i<t.size(); ++i){
		if( s[i] != t[i] ){
			r = i;
			break;
		}
	}

	int rNum = r;
	int ans = -1;
	int anstemp = -1;
	string stemp = s;
	if( rNum != -1)
	{
		{
			stemp[rNum] = t[rNum];
			anstemp = solve( stemp, t, rNum+1, Lcount+1,N);
			if( ans == -1 || anstemp < ans ){
				ans = anstemp;
			}
		}
		{
			stemp = s;
			if( (rNum+1) < stemp.size() ){
				if( stemp[rNum+1] == t[rNum] ){
					stemp.erase(rNum,1);
					anstemp = solve( stemp, t, rNum+1,Lcount+1,N);
					if( ans == -1 || anstemp < ans ){
						ans = anstemp;
					}
				}
			}
		}
		{
			stemp = s;
			stemp.insert( rNum, 1, t[rNum]);
			anstemp = solve( stemp, t, rNum+1,Lcount+1,N);
			if( ans == -1 || anstemp < ans ){
				ans = anstemp;
			}
		}
	}
	else if( rNum == -1)
	{
		{
			stemp = s;
			if( s.size() < t.size() ){
				return Lcount + t.size() - s.size();
			}
			else{
				return Lcount + s.size() - t.size();
			}
		}
	}
	return ans;
}
int main(void){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(6);//

	int N,M;
	string S,T;//[1,1000]
	cin>>N>>M>>S>>T;

	int ans = 0;
	ans = solve(S,T,0,0,max(N,M));
	P(ans);
	return 0;
}
0