[Leaf] [P3147] 262144

p3147-[usaco16open]-262144-p---洛谷">P3147 [USACO16OPEN] 262144 P - 洛谷

1. 题面梗概

中译中：给一个序列，相邻且相等的两个数 $x$ 可以合并成 $x+1$。求最终能合成的最大数字。

$2 \le N \le 262,144$, 初始数值 $\le 40$

2. 逻辑推导

最先想到的是 $O( N^2 )$ 的区间 DP，但 $N$ 达到了 $2.6 \times 10^5$，这就导致规模为 $O(N^2)$ 会炸。

我们尝试换个角度切入，对于任何一个能合成数值 $k$ 的合法区间，存在三个决定性变量：

• 左边界 $i$ | 右边界 $j$ | 合成结果 $k$

注意到 $262144 = 2^{18}$，因此全部合并最大只有 $40 + 18 = 58$。

由于 $k$ 的取值范围小，我们可以把 $k$ 纳入状态维度，从而优化状态设计。

2.1 状态

定义：$f(i, k)$ 为：以 $i$ 为左边界，能够合成数值 $k$ 的右边界。（ 也就是 $j$ ）

合并：合成一个 $k + 1$ 的前提是：找到两个 相邻 且都能合成 $k$ 的区间进行合并。

$$f(i, k + 1) = f( f( i, k ), k )$$

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 262144 + 5;

int f[maxn][60];
int n;

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int ans = 0;
    cin >> n;
    for( int i = 1; i <= n; ++ i )
    {
        int val; cin >> val;
        f[i][val] = i;
        ans = max( ans, val );
    }

    for( int k = 1; k < 60; ++ k )
    {
        for( int i = 1; i <= n; ++ i )
        {
            if( f[i][k] == 0 ) continue;

            if( f[i][k] && f[f[i][k] + 1][k] )
            {
                f[i][k + 1] = f[f[i][k] + 1][k];
                ans = max( ans, k + 1 );
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：$O( V \cdot N )$。

• 碎碎念：数值和位置的状态交换。

• 关联笔记：[[区间DP#状态相关]]