洛谷3147 [USACO16OPEN]262144

双倍经验：洛谷3146

题意

有 $N$ 个正整数，每次可以选相邻的相同的数合并，合并后得到的值为原数 $+1$ 。求合并后最大数的最大值。

其中 $N\le 262144$ 。

题解

用 $f[i][j]$ 表示左端点为 $j$ ，能合并出 $i$ 这个数字的右端点的位置。

显然 $i$ 是由 $i-1$ 转移过来的，所以我们要构造 $f[i-1][?]$ 。

不妨考虑 $i+1$ ，在 $f[i][j]$ 这个右端点基础上再向右合并得到数字 $i$ 的右端点位置即为 $f[i][f[i][j]]$ 。将 $[j,f[i][j]]$ 和 $[f[i][j],f[i][f[i][j]]$ 两段区间合并可以得到 $i+1$ ，即

$$f[i+1][j]=f[i][f[i][j]]$$

意思是从 $j$ 开始合并得到数字 $i+1$ 和从 $f[i][j]$ 开始合并得到数字 $i$ 的右端点相同。

那么对于 $f[i][j]$ ，可以得到状态转移方程式：

$$f[i][j]=f[i-1][f[i-1][j]]$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,f[60][262150],ans;

int main()
{
    n=read();
    for (int i=1;i<=n;i++) f[read()][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=max(ans,i);
        }
    }
    printf("%d",ans);
    return 0;
}