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

题目

题目来源:CCF 四川省选 2004;

在线评测地址:Luogu#5810

题目描述

人们在输入文本时,除了逐个输入这种方式外,还可以利用剪贴板进行复制,如果打入一个字母需要 (1) 的时间,将已输入的部分复制进剪贴板需要 (5) 的时间(Ctrl+ACtrl+C,再取消全选状态),将剪贴板的内容粘贴出来需要 (2) 的时间(Ctrl+V)。

如果我们不关心输入文本的内容,而只关心输入文本的长度,要输入一个长度 不低于 (n) 的文本最少需要多少时间?

输入格式

一个正整数 (n),表示文本的长度。

输出格式

一个正整数 (t),表示需要的最短的时间。

数据规模与约定

评测时间限制 (1000 extrm{ms}),空间限制 (128 extrm{MiB})

  • 对于 (20\%) 的数据,(nle 10)
  • 对于 (60\%) 的数据,(nle 10^4)
  • 对于 (100\%) 的数据,(nle 4 imes 10^4)

分析

题意是说有两种操作,一是用 (1) 的代价插入一个字符,另一个是用 (2u+5) 的代价让所有的字符翻 (u+1) 倍。求得到至少 (n) 个字符的最小代价。

我们选择用 DP 来统计。

(60)-( exttt{pts})

定义 (f_i) 为得到 (i) 个字符的最小代价。

则可以得到 (f_i=maxleft{f_{i-1}+1,max_{d|iland d eq i}left{f_d+frac{2i}{d}+5 ight} ight}),每一次转移都需要遍历整个数列,所以复杂度是 (mathcal{O}(n^2))

(100 exttt{pts})

Solution 1

一个显而易见的优化就是采用 (mathcal{O}(sqrt{n})) 的因数筛法来优化。这种做法就可以通过此题。(似乎这道题的数据规模就是顶着这个算法的)

唯一一个需要注意的点就是要 DP 到 (2n) 的位置再取最大值,因为题目中给出的条件是 不低于 (n)

Solution 2

还有一种 DP 做法采用了不同的状态定义,效率却很高。但是想到这种做法会比较困难,其中样例就是一个坑。

原题中的输入样例是 (20),输出是 (16)。这个样例让我们误以为答案和输入是同等级的……然而完全不是。

如果我们单纯地全选、复制、粘贴,就可以一次在常数花费内将字符数翻倍。所以答案实际上是对数级别的,只不过有大小约为 (7) 的常数而已。

那么,如果我们定义 (f_i)代价(i) 时的最大字符数呢?这样做有很多好处:

  1. 数组长度小,只需要开对数级别的即可;
  2. 答案单调,最后只需要二分搜索就能计算答案。

转移也比较简单,分成增加一个字符和将现有字符翻倍两种情况,分别计算后取最大值就是结果。

复杂度就是 DP 和二分(也可以在统计过程中计算)的总时间。单次 DP 转移需要遍历整个数组,所以就是数组长度的平方 (mathcal{O}(log^2 n))

本做法在 洛谷题解 同步发布。

Solution 3

另一种做法相对暴力一点,但是有很优秀的复杂度。

我们尝试使用数学方法推式子,但是似乎并没有结果。如果我们暴力输出每一个 (n) 的结果,会发现在某个数之后答案会具有规律。

这个数非常小,我们直接前段打表、后段直接计算即可。这种做法在洛谷的 题解区 有提及,这里不再赘述。

Code In C++

这里用了 Solution 2 的做法。DP 数组别忘了开大 (7) 倍哦!

#include <cstdio>
using namespace std;

const int max_n = 120; // 计算公式为 7logn,最好再开大一点
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 的同时遍历求答案
    {
        dp[ans] = dp[ans-1] + 1; // 操作 1:增加一个字符

        for (int i = ans - 7, j = 2; i > 0; i -= 2, j++) // 操作 2:全选+复制(翻倍)
            if (dp[ans] < dp[i] * j)
                dp[ans] = dp[i] * j; // 答案更优就更新
    }

    printf("%d
", ans-1); // 不要忘了减一

    return 0;
}

非常感谢您读完此文章。

如果您喜欢这篇文章,请点一个赞支持一下博主。

如果您对此文有意见,欢迎在评论区留下你的看法,5ab 会尽力达到。

如果您真的不喜欢这篇文章,也请不要喷,5ab 欢迎私信反馈意见。

原文地址:https://www.cnblogs.com/5ab-juruo/p/solution-scoi2004_lg5810.html