洛谷P5810 [SCOI2004] 文本的输入 题解

题目链接：P5810 [SCOI2004] 文本的输入

题意：

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

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

请注意，数据范围与原题略有不同。

输入格式：

一个正整数 $n$，表示文本的长度。

输出格式：

一个正整数 $t$，表示需要的最短的时间。

数据范围：

对于 $100\%$ 的数据，$n\le 4\times 10^4$。

考虑dp。设 $f_i$ 表示花费为 $i$ 的最大价值，转移有两种

• 第一种直接添加一个字符，即（这显然是 $f_i$ 的下界） $$f_i = f_{i-1} + 1$$

• 第二种 copy 一次然后 paste 若干次，即 $$\begin{aligned} f_i\uparrow f_{i - 2u - 5}\times(u+1) \end{aligned}$$ 其中整数 $u$ 满足 $(u \ge 1 \,\land\, i - 2u + 5 \ge 1)$

可以发现，时间复杂度就是答案的大小

容易发现这个数一定小于等于 $7\left\lceil\log _2 n\right\rceil+1$ ，刷过屏的同学们一定很清楚

时间复杂度 $\mathcal{O}(7 \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int dp[233];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, res; cin >> n;
    if(!n) return cout << "0\n", 0;
    for(res = 1; dp[res - 1] < n; ++res)
    {
        dp[res] = dp[res - 1] + 1;
        for(int i = res - 7, j = 2; i > 0; i -= 2, j++)
            if(dp[res] < dp[i] * j) dp[res] = dp[i] * j;
    }
    cout << --res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/5ab-juruo/solution-p5810

你说得对，题解是讲了常规dp方法，但是我一开始想到的就是以花费dp😎。