結果

問題 No.225 文字列変更(medium)
コンテスト
ユーザー IL_msta
提出日時 2015-06-13 19:18:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,998 bytes
コンパイル時間 657 ms
コンパイル使用メモリ 84,912 KB
実行使用メモリ 11,296 KB
最終ジャッジ日時 2024-07-06 19:52:11
合計ジャッジ時間 13,022 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 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( (anstemp != -1) && (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( (anstemp != -1) && (ans == -1 || anstemp < ans) ){
						ans = anstemp;
					}
				}
			}
		}
		{
			stemp = s;
			stemp.insert( rNum, 1, t[rNum]);
			anstemp = solve( stemp, t, rNum+1,Lcount+1,N);
			if( (anstemp != -1) && (ans == -1 || anstemp < ans) ){
				ans = anstemp;
			}
		}
	}
	else if( rNum == -1)
	{
		{
			stemp = s;
			if( s.size() < t.size() ){
				anstemp = Lcount + t.size() - s.size();	
			}
			else{
				anstemp = Lcount + s.size() - t.size();
			}
			if( ans == -1 || anstemp < ans ){
				ans = anstemp;
			}
		}
	}
	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