自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:14:34，当前版本为作者最后更新于2020-08-16 15:02:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

介绍一种比较优秀的 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;
}