2018-2019 ICPC Southwestern European Regional Programming Contest (SWERC 2018) K. Dishonest Driver

Gymは他人のコードを覗けないっぽいのでもしよかったら参考に

まず、区間DPよく知らない人は↓

jupiro.hatenablog.com

のNを見てからだと分かりやすいかも。

dp[i][j] := s[i:j]の時の解とすると、

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]) (k = i, i+1, …, j - 1)

となるのは明らかで、あとはまとめる処理だがこれは一番短い距離の繰り返しに注目したらいいので、lを以下のように定義すると、dp[i][j] = min(dp[i][j], dp[i][l])となる

• s[i:j] がs[i:l]の繰り返しとなる最小のl

さてあとはこのlを求めるパートだが、最初はその位置まで全部一致するかをみて、その後はその長さ分だけ次から一致するかみていけばいい。これはZ-Algorithmで前計算できる。

よって状態数がで遷移がであるので で解くことができました

ll n;
string s;
vector<vector<ll>> dp;

vector<vector<int>> z;

vector<int> Z_Alg(string& S) {
    vector<int> Z_Array(S.size());
    Z_Array[0] = S.size();
    int i = 1, j = 0;
    while (i < S.size()) {
        while (i + j < S.size() && S[j] == S[i + j]) ++j;
        Z_Array[i] = j;
        if (j == 0) { ++i; continue; }
        int k = 1;
        while (i + k < S.size() && k + Z_Array[k] < j) Z_Array[i + k] = Z_Array[k], ++k;
        i += k; j -= k;
    }
    return Z_Array;
}
ll dfs(ll left, ll right) {
    if (dp[left][right] != -1) return dp[left][right];
    ll res = INF;
    for (ll i = left; i < right; i++) {
        chmin(res, dfs(left, i) + dfs(i + 1, right));
    }
    vector<ll> back(n + 1, INF);
    for (ll i = 0; i < right - left; i++) {
        if (back[i + 1] == INF) {
            if (z[left][i + 1] >= i + 1 && (i + 1 ) + i + 1 <= right - left + 1) {
                chmin(back[i + 1 + i + 1], i + 1);
            }
        }
        else {
            if (z[left][i + 1] >= back[i+1] && (i + 1) + back[i + 1] <= right - left + 1) {
                chmin(back[i + 1 + back[i + 1]], back[i + 1]);
            }
        }
    }
    if (back[right - left + 1] != INF) chmin(res, dfs(left, left + back[right - left +1] - 1));
    return dp[left][right] = res;
}

int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */
    scanf("%lld", &n);
    string s; cin >> s;
    z = vector<vector<int>>(n + 1, vector<int>(n + 1));
    for (ll i = 0; i < s.size(); i++) {
        string t = s.substr(i, s.size());
        z[i] = Z_Alg(t);
    }
    dp = vector<vector<ll>>(n + 1, vector<ll>(n + 1, -1));
    for (ll i = 0; i < n; i++) dp[i][i] = 1;
    cout << dfs(0, n - 1) << endl;
    return 0;
}