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

· · 题解

思路

区间 DP 好题。
先把三要素给理出来吧。

状态

我们令 dp_{i,j} 代表从索引 i 出发，能够合成出 j 的最优结束索引 +1。（如果合成不出来，则 dp_{i,j} = 0。）

边界

我们假设 a 是程序中输入进去的数组，那么很明显 dp_{i, a_i} = i + 1。因为从 i 出发已经不需要再合成 a_i。

转移

略有些烧脑了哦。
我们使用倍增思想，考虑 dp_{i,j} 如何转移。
根据题意我们可以得知，要想合成出 j，我们需要两个 j-1 进行合成，或者某个地方本身就有 j（就是动态规划边界）。
所以，我们从 i 出发，要先合成出一个 j-1，因此我们需要知道 dp_{i, j-1}，然后，我们再从 dp_{i, j-1} 位置出发，找到第二个 j-1。最终合并即可。
故动态转移方程如下：

\large dp_{i,j} = dp_{dp_{i, j-1}, j-1}

（注：此处的 \LaTeX 使用了 \large 字号，是由于出现了嵌套的下角标，为了使公式更加清晰故使用。）

代码

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

int ar[510005];
int dp[510005][100];
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i];
        dp[i][ar[i]] = i + 1;
    }
    int ans = 0;
    for(int j = 2; j <= 98; ++j){
        for(int i = 1; i <= n; ++i){
            if(!dp[i][j]) dp[i][j] = dp[dp[i][j - 1]][j - 1];
            if(dp[i][j]) ans = j; //如果可以合成，才记录到答案中
        }
    }
    cout << ans << endl;
    return 0;
}

对了，给大家注明一下此处的 98 是什么：如果真的出现了 5 \times 10^5 \approx 2^{18} 个数，并且每个数都是 80，那么最大也只可能合成 18 + 80 = 98，因此仅循环遍历至 98。

三倍经验：