Submission #570044

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int lcs(string s,string s2,int len) {
	int c[len+1][len+1];	
	int m = s.size();
	int n = s2.size();

	int ret = 0;
	s = ' ' + s;
	s2 = ' ' + s2;

	REP(i,1,m+1) c[i][0] = 0;
	REP(j,1,n+1) c[0][j] = 0;

	REP(i,1,m+1) {
		REP(j,1,n+1) {
			if(s[i] == s2[j]) c[i][j] = c[i-1][j-1] + 1;
			else c[i][j] = max(c[i-1][j],c[i][j-1]);
			ret = max(ret,c[i][j]);
	    }
    }

	return ret;
}

int main() {
	int n;
	cin >> n;

	string s;
	cin >> s;

	int ans = n;
	REP(i, 1, n) {
		string a = s.substr(0, i);
		string b = s.substr(i);

		// cout << a << " " << b << endl;
		// cout << lcs(a, b, 100) << endl;
		//
		int t = lcs(a, b, 100);
		int t2 = n - 2*t;
		ans = min(ans, t2);
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result