항저우전다교 제2장 1012

1012 String Distance dp LCS
http://acm.hdu.edu.cn/showproblem.php?pid=6774
나는 기분이 좋지 않아서 혼자서 미루려고 했는데 결국 잘못 물러났다.결국은 사내의 재능을 보고 고칠 수 있었다.
아주ad hoc,재미없어요.

inline int c2i(const char &ch) {
    return int(ch - 'a');
}

void solve(int kaseId = -1) {
    string s, t;
    cin >> s >> t;
    int s_len(s.length());
    int t_len(t.length());
    s = '$' + s;
    t = '$' + t;

    vector<vint> nx(s_len + 1, vint(26, INF));

    for (int i = s_len; i >= 1; --i) {
        if (i < s_len) nx[i] = nx[i + 1];
        nx[i][c2i(s[i])] = i;
    }

    int q, l, r;
    cin >> q;
    while (q--) {
        cin >> l >> r;
        vint dp(t_len + 1, INF);
        dp[0] = l - 1;

        int lcs = 0;
        for (int i = 1; i <= t_len; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (dp[j] < r && nx[dp[j] + 1][c2i(t[i])] <= r) {
                    dp[j + 1] = min(dp[j + 1], nx[dp[j] + 1][c2i(t[i])]);
                }
                if (dp[j + 1] <= r)lcs = max(lcs, j + 1);
            }
        }
        cout << (r - l + 1 + t_len - lcs * 2) << endl;
    }
}