CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

いつ追加されるんだろうとずっと思ってたけどやっと追加されたので解きます。

問題

code-festival-2015-morning-middle.contest.atcoder.jp

解法

繰り返す文字列は左側と右側に分かれるので, 左からの i 文字と残りの右側 n-i 文字でなるべく長い, 一致する文字列を探せば良いです。これは結局最長共通部分文字列を求める問題に帰着できます。

int dp[111][111];

int solve(string s, string t) {
    int n = s.size(), m = t.size();
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        if (s[i] == t[j]) {
            dp[i+1][j+1] = dp[i][j] + 1;
        } else {
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
        }
    }
    return dp[n][m];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    string s;
    cin >> s;
    int ans = 200;
    for (int i = 0; i < N; i++) {
        int tmp = solve(s.substr(0, i), s.substr(i));
        ans = min(ans, N-2*tmp);
    }
    cout << ans << endl;
    return 0;
}