P3147 [USACO16OPEN] 262144 P

题目

P3147 [USACO16OPEN] 262144 P

算法标签: 动态规划, 线性$dp$, 贪心, 区间$dp$

思路

定义状态表示$f[i][j]$表示左边界是$i$并且合并出的最大值是$j$的右边界是什么位置(开区间), $k$区间覆盖的是$[i,f[i][j]-1]$, 如何进行状态转移?
如果当前状态$f[i][k]=0$, 可以尝试合并两个$k-1$达到当前状态, 设$r=f[i][k-1]$, 那么$f[i][k]=f[r][k-1]$, 如果最后计算出$f[i][k]\ne 0$那么可以记录到答案中, 状态转移依赖$f[i][k-1]$, 可以对$k$从小到大枚举, 递推就能计算出当前状态, 算法时间复杂度$O(nm)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 270010, M = 60;

int n, ans, f[N][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        int val;
        cin >> val;
        f[i][val] = i + 1;
    }

    //以i为左端点合并出数字j的右端点是f[i][j]
    for (int k = 2; k < M; ++k) {
   
        for (int i = 1; i <= n; ++i) {
   
            if (!f[i][k]) f[i][k] = f[f[i][k - 1]][k - 1];
            if (f[i][k]) ans = k;
        }
    }

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

为什么$M=60$

注意到$N=262144$, 也就是$2^{18}$, 每个数的范围不超过$40$, 最大的结果就是$40+18=58$, 向上取整就是$60$