题解 P5810 【[SCOI2004]文本的输入】
5ab_juruo
2020-08-16 15:02:07
本文同步发布于我的 [博客园](https://www.cnblogs.com/5ab-juruo)。
---
介绍一种比较优秀的 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$ 倍哦！
```cpp
#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;
}
```