自动搬运

查看原文

来自洛谷，原作者为

	Yi_chen123 INTP-T || 称呼：逸晨 || 揪捣圈OIer | | 题面 > 数据 > 背锅 > 验题 || 坐标HB || 绿名以上支持私信互关=D || 宣/team/106755

搬运于2025-08-24 21:18:19，当前版本为作者最后更新于2025-06-13 20:33:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

区间 DP 好题。
先把三要素给理出来吧。

状态

我们令 $dp_{i,j}$ 代表从索引 $i$ 出发，能够合成出 $j$ 的最优结束索引 $+1$。（如果合成不出来，则 $dp_{i,j} = 0$。）

边界

我们假设 $a$ 是程序中输入进去的数组，那么很明显 $dp_{i, a_i} = i + 1$。因为从 $i$ 出发已经不需要再合成 $a_i$。

转移

略有些烧脑了哦。
我们使用倍增思想，考虑 $dp_{i,j}$ 如何转移。
根据题意我们可以得知，要想合成出 $j$，我们需要两个 $j-1$ 进行合成，或者某个地方本身就有 $j$（就是动态规划边界）。
所以，我们从 $i$ 出发，要先合成出一个 $j-1$，因此我们需要知道 $dp_{i, j-1}$，然后，我们再从 $dp_{i, j-1}$ 位置出发，找到第二个 $j-1$。最终合并即可。
故动态转移方程如下：

（注：此处的 $\LaTeX$ 使用了 \large 字号，是由于出现了嵌套的下角标，为了使公式更加清晰故使用。）

代码

#include<bits/stdc++.h>
using namespace std;

int ar[510005];
int dp[510005][100];
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++i){
    	cin >> ar[i];
        dp[i][ar[i]] = i + 1;
	}
	int ans = 0;
	for(int j = 2; j <= 98; ++j){
		for(int i = 1; i <= n; ++i){
            if(!dp[i][j]) dp[i][j] = dp[dp[i][j - 1]][j - 1];
            if(dp[i][j]) ans = j; //如果可以合成，才记录到答案中
		}
	}
	cout << ans << endl;
	return 0;
}

对了，给大家注明一下此处的 $98$ 是什么：如果真的出现了 $5 \times 10^5 \approx 2^{18}$ 个数，并且每个数都是 $80$，那么最大也只可能合成 $18 + 80 = 98$，因此仅循环遍历至 $98$。

三倍经验：

• P3146 [USACO16OPEN] 248 G
• P3147 [USACO16OPEN] 262144 P