banner
满五

满五的博客

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

P3147 USACO16OPEN 262144 P Solution

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.

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