[文章目录]
Description
就是给你n个数，然后每次可以合并相邻两个相同的数得到一个+1的数，问最后能得到的最大的数？n<=262144,ai<=40
dp。这道题tonyzhao讲真讲过啊，但是就是不会啊。
考虑状态的设定，如果以区间两个端点+合成的数设定，空间不够，时间上感觉也不行。tonyzhao当时讲的是由于数组存的值很小，不超过40+logn，考虑将数组的第二维和表示能合成的值换一下。
状态设为f[j][i]表示以j为开头，整个区间合成一个i的右端点的值，发现很好转移。f[j][i]=f[f[j][i-1]][i-1].如果为0，则无解。
发现一个卡常数小技能：
将二维数组的第一维设为外层循环，第二维设成内层循环的话常数大概小1/3.
这道题：2732 ms : 808 ms
// 808ms
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,f[65][300000];
int ans=1,mx=1;
int main()
{
scanf("%d",&n); int x;
for(int i=1;i<=n;i++)
{
scanf("%d",&x); mx=max(x,mx);
f[x][i]=i+1;
}
for(int i=1;i<=mx;i++)
for(int j=1;j<=n;j++)
if(f[i][j]&&f[i][f[i][j]])
{
f[i+1][j]=f[i][f[i][j]];
if(i+1>mx) mx=i+1;
}
printf("%d",mx);
return 0;
}