自动搬运

查看原文

来自洛谷，原作者为

	3493441984zz **

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

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

以下是正文

动态规划

其实这题很简单，但是我就是看了题解。。。

这篇题解的思路和其他$dalao$的大同小异，但是这篇主要解释了$58$这个神奇的数字，以及状态转移方程的意思

状态

我们定义$f[i][j]$,里面存的值是左端点为$j$，能合并出$i$这个数字的右端点的位置

那么状态转移方程如下:

为什么呢？

其实这就有点倍增的味道了，我们首先（没有图，自行脑补或者参考其他人的题解$qwq$）

我们先在脑海中画一个数轴$qwq$

然后最左边的一个点位置为$j$

那么我们可以求出$f[i-1][j]$，也就是从$j$往后一直合并到哪个位置，可以最终合并出$i-1$，这个位置其实就是$f[i-1][j]$

那么我们接下来呢？

我们从这个位置继续向后，看看到哪个位置又能合并出一个$i-1$，那么找到这个点，其实就是$f[i-1][f[i-1][j]]$,我们合并到这里的时候，就会合并出两个相邻的$i-1$，那么不就可以合并出一个$i$了吗？

所以，状态转移就是$$f[i][j]=f[i-1][f[i-1][j]]$$

接下来是美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#define N 61
#define M 270007
using namespace std;
int n,ans;
int f[N][M];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
	{
		int in;
		scanf("%d",&in);
		f[in][i]=i+1;
	}
    for(int i=2;i<=58;++i)//58?????
        for(int j=1;j<=n;++j)
        {
            if(!f[i][j]) 
				f[i][j]=f[i-1][f[i-1][j]];
            if(f[i][j]) 
				ans=i;
        }
    printf("%d",ans);
}

那么上面这个神奇的$58$呢？

其实就跟数据范围有关

我们看到$2≤N≤262144$，而我们像倍增一样合并，那么因为$2^{18}=262144$

而数字的大小在$1-40$之间，那么产生的数最多也就是$40+18=58$啦

如果有错误，请私信我或者评论留言~~（而我不会看）~~