17564번: Dishonest Driver

\(\mathrm{dp[}i\mathrm{][}j\mathrm{]}\)는 구간 \((i, j]\)의 문자열에 대한 답과 그 문자열을 최대 몇개의 동일한 부분 문자열로 분할할 수 있는지를 저장한다.

 

\(\mathrm{dp[}i\mathrm{][}i\mathrm{]=1}\)

 

\(\displaystyle\mathrm{dp[}i\mathrm{][}j\mathrm{]}=\min_{k=i+1}^{j-1}\mathrm{(dp[}i\mathrm{][}k\mathrm{]}+(0\:\mathrm{or}\:\mathrm{dp[}k\mathrm{][}j\mathrm{]))}\)

 

구간 \((i, k]\)문자열과 \((k, j]\)문자열의 반복된 부분이 같다면 \(\mathrm{0}\)

그렇지 않으면 \(\mathrm{dp[}k\mathrm{][}j\mathrm{]}\)를 취한다.

 

위 부분을 효율적으로 하기 위해서 모든 부분 문자열은 미리 정수 id로 매핑한 후, 새로운 공간에 각 부분문자열의 id를 저장했다. \(O(n^3)\)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
pi dp[701][701];
bool v[701][701];
int t[701][701];
int n; string s;
map<string, int> mp;
pi solve(int i, int j) {
    if (v[i][j] > 0) return dp[i][j];
    if (i + 1 == j) {
        dp[i][j] = {1, 1};
        v[i][j] = true;
        return dp[i][j];
    }
    int ans = INT_MAX;
    int rep = 1;
    for (int idx = i + 1; idx < j; idx++) {
        pi first = solve(i, idx), second = solve(idx, j);
        if (t[i + 1][(idx - i) / first.second] == t[idx + 1][(j - idx) / second.second]) ans = min(ans, first.first), rep = first.second + second.second;
        else ans = min(ans, first.first + second.first);
    }
    dp[i][j] = {ans, rep};
    v[i][j] = true;
    return dp[i][j];
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s; s = " " + s;
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) mp[s.substr(i, j - i + 1)] = idx++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) t[i][j - i + 1] = mp[s.substr(i, j - i + 1)];
    }
    cout << solve(0, n).first << "\n";
    return 0;
}