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

P3147 USACO16OPEN 262144 P Solution

DP Series.


Read the problem statement on Luogu

Merge adjacent identical numbers and increment the result by one. Find the maximum value obtained.


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).


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,

    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++){
            DP[i][j] = DP[i-1][DP[i-1][j]];
            ans = i;

Note that we are doubling the merge, so $log_2{262144} + 40 = 58$ is the maximum value that can be obtained.


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.


This problem is about optimizing interval DP. The journey of learning DP is long, and more practice is needed.

Ownership of this blog data is guaranteed by blockchain and smart contracts to the creator alone.