DP Series.
Problem Description#
Look at the problem, Luogu
Merge adjacent identical numbers and increment the number by one. Find the maximum value obtained.
Analysis#
The initial thought is to use basic interval DP, without further explanation:
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;
But $2 \leq n \leq 262144 $, which obviously leads to MLE (Memory Limit Exceeded).
Optimization#
Based on the idea, we find that we can use a method similar to doubling.
Use state f[i][j] to represent the left endpoint position of the interval with the result being i and the right endpoint being j. If the value is 0, it means it is not feasible.
Because the problem requires finding two adjacent equal intervals and merging them, we have:
f[i][j] = f[i-1][f[i-1][j]];
Split f[i][j] into two intervals that can be merged into i-1
That is
f[i-1][j]
|------<i-1>-----|----<i-1>-----|
j f[i-1][f[i-1][j]]
If f[i-1][j] or f[i-1][f[i-1][j]] is not feasible, f[i][j] is not feasible, that is, it is transferred to 0
How do we represent the result?
Record ans and update ans if f[i][j] is feasible. Since i is increasing, we do not need the max operation.
We have
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;
}
}
}
Note that we are doubling the merge, so $log_2{262144} + 40 = 58$ is the maximum value that can be obtained.
Initialization#
Obviously, not merging is feasible, so when inputting, initialize
for(int i = 1; i<=N; i++){
int in;
cin >> in;
DP[in][i] = i+1;
}
Regarding i+1: To avoid overlapping intervals, the interval represented by f[i][j] is a left-closed right-open interval, so the right endpoint is i+1.
Summary#
This problem is about optimizing interval DP. The journey of learning DP is long, and more practice is needed.