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$