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.