  # 满五的博客

Non-Binary | High School | OI | Code | Photography | etc. 独立开发者、摄影/文学/电影爱好者 English/中文，日本語を勉強しています INFP | they

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.