题解 P5810 【[SCOI2004]文本的输入】

· · 题解

本文同步发布于我的 博客园。

介绍一种比较优秀的 DP 做法。

一般的思路会用 f_i 表示当目标为 i 时的最小代价。这种做法经过优化后可以达到 O(n\sqrt{n}) 的复杂度。

但是如果定义 f_i 为 代价 为 i 时的最大字符数呢？（即下标和值互换）

考虑几种操作：

添加字符

直接从 f_{i-1} 转移即可。

复制、粘贴

直接遍历之前的 f_{i-k}（k=2u+5，u\in \mathbb{N^{*}}）：

f_i=\max_{u=1}^{k=2u+5\le i} {(u+1)f_{i-k}}

将这两步取最大值即可。

最后，可以证明 f_i 是单调的，直接二分搜索即可。

复杂度？

首先，可以证明答案 \le 7\left\lceil\log_2n\right\rceil+1（加入一个字符后不停复制粘贴即可），也就是说答案上限是 \mathcal{O}(\log n) 的。

所以，DP 数组只需要开 \mathcal{O}(\log n) 大小。

同时，单步转移复杂度是 \mathcal{O}(\text{DP 数组大小})=\mathcal{O}(\log n)，整体复杂度就是 \mathcal{O}(\log^2 n)，可以轻松通过。

Code

DP 数组别忘记开大 7 倍哦！

#include <cstdio>
using namespace std;

const int max_n = 120;
int dp[max_n] = {};

int main()
{
    int n, ans;

    scanf("%d", &n);

    if (n == 0)
    {
        puts("0");
        return 0;
    }

    for (ans = 1; dp[ans-1] < n; ans++)
    {
        dp[ans] = dp[ans-1] + 1;

        for (int i = ans - 7, j = 2; i > 0; i -= 2, j++)
            if (dp[ans] < dp[i] * j)
                dp[ans] = dp[i] * j;
    }

    printf("%d\n", ans-1);

    return 0;
}