P3147 USACO16OPEN 262144 P 题解

DP 系列。

题面

看题,Luogu

合并相邻的相同数字,变成数字加一。求获得的最大值。

思考

最初想到的是基础的区间 DP,不做解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
long long ans = 0;
for(int len = 2; len<=N; len++){
for(int i = 1; i+len-1<=N; i++){
int y = i+len-1;
for(int k = i; k<y; k++){
if(DP[i][k] == DP[k+1][y]){
DP[i][y] = max(DP[i][y], DP[i][k] + 1);
}
}
ans = max(ans, DP[i][y]);
}
}
cout << ans << endl;

但是 $ 2 \leq n \leq 262144 $ ,显然会 MLE。

优化

借鉴思路,我们发现可以使用类似倍增的方法去做。

用状态 f[i][j] 表示 合成之后结果为 i,右端点为 j 的区间的左端点位置,如果 值为 0 即 不可行。

因为题目要找两个相邻相等的区间,合成。有:

1
2
3
f[i][j] = f[i-1][f[i-1][j]];

把 f[i][j] 拆分成两个能合成为 i-1 的区间

1
2
3
4
5
                 f[i-1][j]
|------<i-1>-----|----<i-1>-----|
j f[i-1][f[i-1][j]]

如果 f[i-1][j] 或 f[i-1][f[i-1][j]] 不成立,f[i][j] 就不成立,即转移为 0

那如何表示结果?

记录 ans,如果 f[i][j] 可行,就更新 ans。因为 i 递增,所以不需要 max 操作。

得到

1
2
3
4
5
6
7
8
9
10
for(int i =2; i<=58; i++){
for(int j = 1; j<=N; j++){
if(!DP[i][j]){
DP[i][j] = DP[i-1][DP[i-1][j]];
}
if(DP[i][j]){
ans = i;
}
}
}

注意我们倍增合并,所以 $log_2{262144} + 40 = 58$ 是可能获得的最大值。

初始化

显然不合并是可行的,所以在输入的时候,初始化

1
2
3
4
5
for(int i = 1; i<=N; i++){
int in;
cin >> in;
DP[in][i] = i+1;
}

关于 i+1:为了避免区间重复,我们 f[i][j] 表示的区间是左闭右开区间,所以右端点是 i+1

小结

这道题是区间 DP 状态优化,DP 学习之路漫漫,还需要多加练习。