Introduction

Dynamic programming problems that rely on transitions between adjacant elements often cannot be solved using standard DP approaches. In such cases, linear segment DP proves useful. Also known as continuous segment DP, this technique focuses on maintaining the total contribution of various continuous segments that satisfy specific conditions.

The core idea of linear segment DP is to represent states in a way that allows efficient transitions by considering only the endpoints of segments. This approach enables the use of bijections with permutations and facilitates solving problems where dependencies exist among neighboring items.

Typically, we define dp[i][j] as the number of ways to process the first i elements forming exactly j valid segmants — referred to as "lines". These lines can be updated through three operations:

• Creating a new line: dp[i][j] += dp[i-1][j-1]
• Extending an existing line: dp[i][j] += dp[i-1][j]
• Merging two lines: dp[i][j] += dp[i-1][j+1]

Kangaroo Problem

First, consider the case without constraints s and t. Each element must either be greater than or less than its neighbors. We can model this using the above transitions.

Let dp[i][j] denote the number of ways to form j lines from the first i elements. As we add elements in ascending order, transitions occur as follows:

• dp[i][j] = dp[i-1][j-1] * j: A new segment is formed by inserting into one of the j available posisions.
• dp[i][j] = dp[i-1][j+1] * j: Two segments merge, assuming the current element is larger than previous ones.

When s and t are introduced:

• If i == s or i == t, then dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
• If i > s, no new head can be added.
• If i > t, no tail can be appended.

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e3, Mod = 1e9 + 7;
int n, l, r;
int dp[N][N];

signed main(){
    cin >> n >> l >> r;
    dp[1][1] = 1;
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= n; j++){
            if(i == l || i == r)
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % Mod;
            else{
                dp[i][j] = dp[i - 1][j - 1] * j % Mod;
                if(l < i) dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + Mod) % Mod;
                if(r < i) dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + Mod) % Mod;
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1] * j % Mod) % Mod;
            }
        }
    cout << dp[n][1] << endl;
    return 0;
}

High-Rise Building Street

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 105, Mod = 1e9 + 7;
int n, l, a[N], dp[2][N][1005][2][2];

bool cmp(int x, int y){return x > y;}
void add(int& u, int v){
    u %= Mod, v %= Mod;
    u = (u + v + Mod) % Mod;
    return ;
}

signed main(){
    cin >> n >> l;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, cmp);
    
    // dp[i & 1][cnt][sum][left][right] represents:
    // number of ways to consider a[i], with cnt segments, sum of heights, fixed left/right boundaries
    dp[1][1][0][0][0] = 1; dp[1][1][0][0][1] = 1;
    dp[1][1][0][1][0] = 1; dp[1][1][0][1][1] = 1;
    
    for(int i = 2; i <= n; i++){
        bool u = i & 1, v = !u; // current and previous states
        
        // Clear current state
        for(int cnt = 1; cnt <= i; cnt++) for(int sum = 0; sum <= l; sum++)
            dp[u][cnt][sum][0][0] = 0, dp[u][cnt][sum][0][1] = 0, 
            dp[u][cnt][sum][1][0] = 0, dp[u][cnt][sum][1][1] = 0;
            
        for(int cnt = 1; cnt < i; cnt++) for(int sum = 0; sum <= l; sum++)
            for(int L = 0; L <= 1; L++)
                for(int R = 0; R <= 1; R++){
                    int newSum = sum + (a[i - 1] - a[i]) * (2 * cnt);
                    if(L) newSum -= (a[i - 1] - a[i]);
                    if(R) newSum -= (a[i - 1] - a[i]);
                    if(l < newSum) continue;
                    
                    // Inserting a new segment or merging segments
                    if(cnt != 1) add(dp[u][cnt + 1][newSum][L][R], (cnt - 1) * dp[v][cnt][sum][L][R]);
                    if(cnt != 1) add(dp[u][cnt - 1][newSum][L][R], (cnt - 1) * dp[v][cnt][sum][L][R]);
                    
                    // Adding new segments at ends
                    if(!L) add(dp[u][cnt + 1][newSum][0][R], dp[v][cnt][sum][0][R]), 
                           add(dp[u][cnt + 1][newSum][1][R], dp[v][cnt][sum][0][R]);
                    if(!R) add(dp[u][cnt + 1][newSum][L][0], dp[v][cnt][sum][L][0]), 
                           add(dp[u][cnt + 1][newSum][L][1], dp[v][cnt][sum][L][0]);
                    
                    // Extending existing segments
                    if(cnt != 1) add(dp[u][cnt][newSum][L][R], 2 * (cnt - 1) * dp[v][cnt][sum][L][R]);
                    if(!L) add(dp[u][cnt][newSum][0][R], dp[v][cnt][sum][0][R]), 
                           add(dp[u][cnt][newSum][1][R], dp[v][cnt][sum][0][R]);
                    if(!R) add(dp[u][cnt][newSum][L][0], dp[v][cnt][sum][L][0]), 
                           add(dp[u][cnt][newSum][L][1], dp[v][cnt][sum][L][0]);
                }
    }
    
    int ans = 0;
    for(int i = 0; i <= l; i++) add(ans, dp[n & 1][1][i][true][true]);
    cout << ans << endl;
    return 0;
}