DP Series.
Problem
Read the problem statement on Luogu
Merge adjacent identical numbers and increment the result by one. Find the maximum value obtained.
Approach
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;
However, since $2 \leq n \leq 262144$, it will obviously result in MLE (Memory Limit Exceeded).
Optimization
Based on the approach, we can use a similar method to doubling.
Use state f[i][j] to represent the left endpoint position of the interval with the result as i and the right endpoint as j, where a value of 0 means it is not feasible.
Since 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, and the transition is set to 0
How do we represent the result?
Record ans and update it 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
It is obviously feasible not to merge, so initialize it when inputting:
for(int i = 1; i<=N; i++){
int in;
cin >> in;
DP[in][i] = i+1;
}
Regarding i+1: to avoid overlapping intervals, we represent the interval of f[i][j] as 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.