262144 P

题目描述

游戏一开始有\(n\)个正整数，\((2<=n<=262144)\)，范围在\(1-40\)。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个7合并成一个8)，目标是使得最大的数最大，请帮助Bessie来求最大值

思路

我们假设所有的数全是\(40\)那么最大可以合成出来的数是\(58\),可作为数组的一维

定义\(f[i][j]\)为能合成出来\(i\)，且左端点为\(j\)的情况下的区间长度/右端点，右端点比区间长度稍简单一点，这里采用右端点的情况

状态转移方程：\(f[i][j] = f[i-1][f[i-1][j]]\)

这里有类似倍增的意思，\(f[i-1][j]\)是以\(j\)为左端点，能合成出\(i-1\)的右端点，那\(f[i-1][f[i-1][j]]\)就是以上一个右端点作为下一次左端点再往后找，那么就是两个\(i-1\)合成了\(i\)

初始化/区间开闭问题

\(f[a[i]][i]] = i + 1\)，这里要定义为左闭右开的区间

举个例子如果是两个\(1\)要合成\(2\)，那么\(f[2][1] = f[1][f[1][1]]\)如果不加1的话，它更新完就还是1没法扩展过去，更离谱的是：如果不加1，且一共只有一个数的情况下，它甚至可以自己左脚踩右脚一直往上增，所有的\(f[n][1]\)都会被更新，考虑完上面的情况就可以直接给出代码

洛谷P3147

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 262145;
int ans,n,f[60][maxn];//f(i,j)表示能合成i,左端点为j情况下的右端点(左闭右开区间) 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		f[x][i] = i + 1;
	}
	for(int i=1;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;
		}
	}
	printf("%d",ans);
	return 0;
}