[LGOJ]P3147 [USACO16OPEN]262144 P

这是一个有一点思维难度的题（至少我这么认为）

首先我们定义$f[i][j]$表示以$j$为左端点合成出$i$的右端点位置

那么我们可以求出$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]]$$

至于$i$的循环范围，注意到题目中$2<=n<=262144$,而$262144=2^{58}$,并且最大数为$40$,所以循环$40+18=58$即可
于是我们就非常愉快地得到了代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,ans;
int a[maxn],f[60][maxn];
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
int main()
{
	n=read();
	for (int i=1;i<=n;i++)
	{
		a[i]=read();
		f[a[i]][i]=i+1;
	}
	for (int i=2;i<=58;i++)
	{
		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;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}