P3446 [POI2006]EST-Aesthetic Text

Alex_Wei · 2021-12-13 16:58:14 · 题解

*P3446 [POI2006]EST-Aesthetic Text

POI 合集。

还算有趣的动态规划。遇到这种区间划分题首先考虑 DP，设 f_{i,j} 表示以第 i 个单词结尾为一行，且这一行长度为 j 的最小答案，那么有 f_{i,j}=\min_{\\k=1}^m(f_{p,k}+|j-k|)，其中 p 满足 i-p-1+\sum_{\\q=p+1}^i l_q=j。直接转移的复杂度为 \mathcal{O}(n^2m)（枚举 p 算出对应的 j）。

不过我们注意到有很多 j 都是空值，说明这个定义有些劣。不妨修改定义，设 f_{i,j} 表示最后一行为 i-j+1\sim i 的答案，再设 L_{i,j} 表示 j-1+\sum_{\\p\in [i-j+1,i]}l_p 即 i-j+1\sim i 组成一行的长度，那么有：

此时时间复杂度优化为 \mathcal{O}(n^3)，但仍无法接受。接下来使用拆绝对值的技巧，即维护 pre_{i,j} 表示 f_{i,j}-L_{i,j}，suf_{i,j} 表示 f_{i,j}+L_{i,j}，那么对于 f_{i,j} 对应的转移位置 i-j，我们只需找到最后一个位置 p 使得 L_{i-j,p}\leq L_{i,j}，那么 f_{i,j} 可以由 pre_{i,p} 关于 p 的前缀 \min 加上 L_{i,j}，以及 suf_{i,p+1} 关于 p 的后缀 \min 减去 L_{i,j} 得到。

又因为固定 i-j 时，L_{i,j} 随着 i 增大而增大，这说明 f_{i+k,j+k} 从 i-j 处转移时的 p 随着 k 增加而递增，因此对每个位置 i 在求出 f_{i,j} 维护一个转移指针即可做到平方。

const int N = 2e3 + 5;
int n, m, ans = 2e9, L[N], pos[N], tot[N], f[N][N];
int len[N][N], pre[N][N], suf[N][N];
int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i++) {
        cin >> L[i], L[i] += L[i - 1];
        for(int j = i - 1; ~j; j--) {
            int cur = i - j - 1 + L[i] - L[j];
            if(cur > m) break; tot[i]++;
            if(!j) f[i][tot[i]] = 0;
            else {
                f[i][tot[i]] = 2e9;
                while(pos[j] < tot[j] && len[j][pos[j] + 1] <= cur) pos[j]++;
                if(pos[j]) cmin(f[i][tot[i]], pre[j][pos[j]] + cur);
                if(pos[j] < tot[j]) cmin(f[i][tot[i]], suf[j][pos[j] + 1] - cur);
            } len[i][tot[i]] = cur;
        } pre[i][0] = suf[i][tot[i] + 1] = 2e9;
        for(int j = 1; j <= tot[i]; j++) pre[i][j] = min(pre[i][j - 1], f[i][j] - len[i][j]);
        for(int j = tot[i]; j; j--) suf[i][j] = min(suf[i][j + 1], f[i][j] + len[i][j]);
        if(i == n) for(int j = 1; j <= tot[n]; j++) cmin(ans, f[i][j]);
    } cout << ans << endl;
    return 0;
}