嘘~ 正在从服务器偷取页面 . . .

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

发布日期: 2024-02-20

更新日期: 2024-02-20

文章字数: 563

洛谷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;
}