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

P3147 USACO16OPEN 262144 P Solution

DP Series.

Problem Description#

Look at the problem, Luogu

Merge adjacent identical numbers and increment the number 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;

But $2 \leq n \leq 262144 $, which obviously leads to MLE (Memory Limit Exceeded).


Based on the idea, we find that we can use a method similar to doubling.

Use state f[i][j] to represent the left endpoint position of the interval with the result being i and the right endpoint being j. If the value is 0, it means it is not feasible.

Because 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, that is, it is transferred to 0

How do we represent the result?

Record ans and update ans 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.


Obviously, not merging is feasible, so when inputting, initialize

for(int i = 1; i<=N; i++){
    int in;
    cin >> in;
    DP[in][i] = i+1;

Regarding i+1: To avoid overlapping intervals, the interval represented by f[i][j] is 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 post data is guaranteed by blockchain and smart contracts to the creator alone.