Codeforces 938F. Erasing Substrings

题意：

给你一个长度为$n$的字符串$s$，你要对它进行$k = \lfloor \log_2n \rfloor$次操作。第$i$次操作中，你要删除$s$中长度恰好为$2 ^ {i - 1}$的字串。求最后字典序最小的字符串。

题解：

首先考虑一个朴素的dp，$f_{i, j}$表示前$i$位删去了$j$位的最小串，从$f_{i - 1, j}$或$f_{i - 2 ^ k, j - 2 ^ k}$转移。状态$n ^ 2$，但是转移是$n\log n$的。考虑如何优化。显然，对于所有表示串长度一样的$f$（即$i - j$相等），只有那些字典序最小的是有用的，因为我们每次是在后面扩展一位，不会让字典序更小。所以我们修改状态：$f_{i, j}$表示前$i$位删去了$j$位是否是字典序最小的。先枚举$i - j$，然后找出最小的$s_{i + 1}(f_{i, j} = true)$，更新$f_{i + 1, j}$，再用它们更新$f_{i + 1 + 2 ^ k, j + 2 ^ k}$。做完了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

string s, ans;
int n;
bool f[5010][4100];

int main()
{
    ios::sync_with_stdio(false);
    cin >> s;
    n = s.length();
    for (int i = 0; i < n; i++) f[i][i] = true;
    int hh = 1;
    while (hh + hh <= n) hh += hh;
    int nn = n - hh + 1;
    // cerr << hh << endl;
    for (int l = 0; l < nn; l++)
    {
        char mn = 127;
        for (int i = l; i <= n; i++)
        {
            int j = i - l;
            if (j >= hh) break;
            if (f[i][j]) mn = min(mn, s[i]);
        }
        ans += mn;
        for (int i = l; i <= n; i++)
        {
            int j = i - l;
            if (j >= hh) break;
            if (f[i][j] && s[i] == mn)
            {
                f[i + 1][j] = true;
            }
        }
        for (int i = l + 1; i <= n; i++)
        {
            int j = i - l - 1;
            if (j >= hh) break;
            if (f[i][j]) continue;
            for (int k = 1; k < hh; k += k)
                if ((j & k) && f[i - k][j - k])
                {
                    f[i][j] = true;
                    break;
                }
        }/*
        cerr << "l = " << l << " mn = " << mn << endl;
        for (int i = l + 1; i <= n; i++)
        {
            int j = i - l - 1;
            if (j >= hh) break;
            if (f[i][j])
                cout << i << ' ' << j << endl;
        }*/
    }
    cout << ans << endl;
}