题解：B4280 [蓝桥杯青少年组国赛 2023] 数学实验

· · 题解

\textup{P9049 [PA 2021] Mopadulo}

li\textup{N}k

知识点：动规，倍增。

\textup{Description}

给定数列，将其中相邻两个相同的数合并而替换成一个大一的数。

求：最终序列中最大的数的最大化。

\textup{Solution}

第一次写这种格式的题解，花了我快 2h，建议先阅读提示自己思考。

与简化版 \textcolor{skyblue}{249}-1 没什么关系，于是不提及。

:::info[\textup{First and foremost}] 想到 dp 不难，但是状态？

区间会炸，想想如何改改状态解决？

是否可以将区间右端点转化成什么？ :::

:::success[\textup{Answer.1}] 与前人类似地定义 dp_{k, i} 表示从第 i 位开始合并出 k 的右端点下标 +1。

注意此处是左闭右开。

至于为什么？

其实是方便转移和初始化，将两个序列合并的时候就容易了。

最后是若合并不出则值为 0。 :::

:::info[\textup{Subsequently}] 考虑如何转移。

想一下合并出一个数的条件？

可以往倍增那种嵌套的转移去想。 :::

::::success[\textup{Answer.2}] 需要合并出一个数 k，前提是要有两个 k-1。

那么找到上一个 k-1，从那里往后去合成 k。

所以此处有：

\large dp_{k, i} = dp_{k - 1, \textcolor{red}{dp_{k - 1, i}}}

:::info[\textup{Thanks}]{open} 由于一直找不到很好的方式体现，此处角标书写格式借鉴置顶大佬的题解并加以颜色区别。

并致以感谢。 ::: ::::

:::info[\textup{Additionally}] 接下来要讲的是：

可以先自己想一下再看。 ::: :::success[\textup{Answer.3}] 首先是初始化，就是自己到自己，即：

dp_{a_i, i} = i + 1

答案即为能合并出来的最大值。

而循环的边界条件约为 98，这是由于在边界时 5 \times 10^5 时，每个数都是最大值 80。

此时最多合并出最大值 \log_2 \cdot (5 \times 10 ^ 5) \approx 18.93 再加上原本 80 得到 98。 :::

:::warning[\textup{Tips}] 注意神秘的数组大小，不要像我一样开多大 DTL 就跑到多大。

小心类似 CPH 评测跑出来不容易发现数组越界问题，请使用 Dev。 :::

:::success[\textup{Code}]

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 249;
const int DTL = 249;
int N, ans;
int a[MAXN], dp[DTL][MAXN];
int main(){
    cin >> N;
    for( int i = 1; i <= N; i ++ ){
        cin >> a[i];
        dp[a[i]][i] = i + 1;//初始化
    }
    for( int k = 2; k <= ( DTL - 49 ) / 2; k ++ ){//这里就是98
        for( int i = 1; i <= N; i ++ ){
            if( !dp[k][i] ) dp[k][i] = dp[k - 1][dp[k - 1][i]];
            //此处我尝试用max并且过了，数据过水，因为取max没有正确性吧。
            //贪心来说，应该找最小可能的点才有足够的正确性。
            if( dp[k][i] ) ans = max( ans, k );//统计答案
        }
    }
    cout << ans;
    return 0;
}

:::

:::info[\textup{Last but not the least}]

审核管理员辛苦了，如果您有什么看不懂、我太弱了所以讲错了的地方，请您在评论区指出或着私信我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗?

谢谢你看到这里~ :::