Merging Strings for Maximum Palindromes

Given two strings $S1$ and $S2$, we aim to merge them into a single string $S3$ while maintaining the relative order of characters from the original strings. The goal is to find the maximum possible length of a palindromic substring within any such $S3$.

A four-dimensional dynamic programming approach can track whether a segment formed by $S1[i..j]$ and $S2[k..l]$ constitutes a palindrome. Let dp[i][j][k][l] be a boolean indicating this property.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int solve_palindrome_merge() {
    string s1, s2;
    if (!(cin >> s1 >> s2)) return 0;
    int n = s1.length(), m = s2.length();
    static bool dp[55][55][55][55];
    int max_len = 0;

    for (int len1 = 0; len1 <= n; ++len1) {
        for (int len2 = 0; len2 <= m; ++len2) {
            for (int i = 1; i + len1 - 1 <= n; ++i) {
                for (int k = 1; k + len2 - 1 <= m; ++k) {
                    int j = i + len1 - 1, l = k + len2 - 1;
                    bool &res = dp[i][j][k][l];
                    res = false;
                    if (len1 + len2 <= 1) res = true;
                    else {
                        if (s1[i-1] == s1[j-1] && len1 > 1) res |= dp[i+1][j-1][k][l];
                        if (s1[i-1] == s2[l-1] && len1 > 0 && len2 > 0) res |= dp[i+1][j][k][l-1];
                        if (s2[k-1] == s1[j-1] && len1 > 0 && len2 > 0) res |= dp[i][j-1][k+1][l];
                        if (s2[k-1] == s2[l-1] && len2 > 1) res |= dp[i][j][k+1][l-1];
                    }
                    if (res) max_len = max(max_len, len1 + len2);
                }
            }
        }
    }
    return max_len;
}

Sequence Selection with Positional Multipliers

Consider a sequence $A$ of length $n$. In each step, you remove a number from either the left or right end. The score for the $k$-th selection is $A_{chosen} \times B_k$, where $B$ is a sequence of multipliers. We seek to maximize the total score.

The state dp[i][j] represents the maximum score obtained from the sub-interval $[i, j]$. Since the total number of elements picked is $n - (j - i + 1)$, we can determine which multiplier $B$ to use based on the current interval length.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long maximize_score() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];

    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));
    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            int multiplier = b[n - len + 1];
            dp[i][j] = max(dp[i + 1][j] + (long long)a[i] * multiplier, 
                           dp[i][j - 1] + (long long)a[j] * multiplier);
        }
    }
    return dp[1][n];
}

When scaling this to a matrix where you pick from each row independently and the multiplier is $2^k$, high-precision arithmetic is required. The logic remains the same per row, and the results are summed.

Minimum Energy Consumption for Task Scheduling

In a scenario where tasks (like shutting down street lights) are positioned along a 1D line, a worker moves at $1 m/s$. Each task consumes energy per second until it is completed. We need the minimum total energy spent.

This is a classic interval DP where the state must include the worker's current position (at the left or right boundary of the completed interval).

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
long long dp[MAXN][MAXN][2]; // 0 for left, 1 for right
int pos[MAXN], weight_sum[MAXN];

void solve_energy_min() {
    int n, start_idx;
    while (cin >> n >> start_idx) {
        for (int i = 1; i <= n; ++i) {
            int w;
            cin >> pos[i] >> w;
            weight_sum[i] = weight_sum[i-1] + w;
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[start_idx][start_idx][0] = dp[start_idx][start_idx][1] = 0;

        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                int j = i + len - 1;
                long long total_w = weight_sum[n] - (weight_sum[j] - weight_sum[i-1]);
                
                // Arriving at i from previous state
                dp[i][j][0] = min(dp[i+1][j][0] + (long long)(pos[i+1] - pos[i]) * (total_w + weight_sum[i+1] - weight_sum[i]),
                                  dp[i+1][j][1] + (long long)(pos[j] - pos[i]) * (total_w + weight_sum[i+1] - weight_sum[i]));
                
                // Arriving at j from previous state
                dp[i][j][1] = min(dp[i][j-1][1] + (long long)(pos[j] - pos[j-1]) * (total_w + weight_sum[j] - weight_sum[j-1]),
                                  dp[i][j-1][0] + (long long)(pos[j] - pos[i]) * (total_w + weight_sum[j] - weight_sum[j-1]));
            }
        }
        cout << min(dp[1][n][0], dp[1][n][1]) << endl;
    }
}

Maximal Sub-rectangle Sum in a 2D Grid

To find the sub-rectangle with the largest sum in an $N \times N$ grid, we compress the 2D problem into a 1D Maximum Subarray Sum problem. By fixing the top and bottom row boundaries, we sum the columns between these rows to create a 1D array.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int max_subrectangle() {
    int n; cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) cin >> grid[i][j];

    int global_max = -1e9;
    for (int top = 0; top < n; ++top) {
        vector<int> col_sums(n, 0);
        for (int bottom = top; bottom < n; ++bottom) {
            int current_kadane = 0;
            for (int k = 0; k < n; ++k) {
                col_sums[k] += grid[bottom][k];
                current_kadane = max(col_sums[k], current_kadane + col_sums[k]);
                global_max = max(global_max, current_kadane);
            }
        }
    }
    return global_max;
}

Maximal Alternating Pattern (Chessboard) Areas

For a grid of black (0) and white (1) cells, we want to find largest square and rectangle where adjacent cells always differ in color. This is solved using the "Suspension Line" (or Histogram) method.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void checkerboard_optimization() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> mat(n + 1, vector<int>(m + 1));
    vector<vector<int>> h(n + 1, vector<int>(m + 1, 1));
    vector<vector<int>> left_bound(n + 1, vector<int>(m + 1));
    vector<vector<int>> right_bound(n + 1, vector<int>(m + 1));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> mat[i][j];
            left_bound[i][j] = right_bound[i][j] = j;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= m; ++j)
            if (mat[i][j] != mat[i][j-1]) left_bound[i][j] = left_bound[i][j-1];
        for (int j = m - 1; j >= 1; --j)
            if (mat[i][j] != mat[i][j+1]) right_bound[i][j] = right_bound[i][j+1];
    }

    int max_sq = 0, max_rect = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i > 1 && mat[i][j] != mat[i-1][j]) {
                h[i][j] = h[i-1][j] + 1;
                left_bound[i][j] = max(left_bound[i][j], left_bound[i-1][j]);
                right_bound[i][j] = min(right_bound[i][j], right_bound[i-1][j]);
            }
            int width = right_bound[i][j] - left_bound[i][j] + 1;
            int side = min(h[i][j], width);
            max_sq = max(max_sq, side * side);
            max_rect = max(max_rect, h[i][j] * width);
        }
    }
    cout << max_sq << "\n" << max_rect << endl;
}

Efficient State Compression for Value Merging

In a sequence where adjacent equal values $v$ can be merged into $v+1$, finding the maximum possible value for a large sequence ($N \appprox 262,144$) requires optimizing space. Since values are small ($1..40$), we can use the value as part of the state.

Let dp[v][l] be the right endpoint $r$ such that the interval $[l, r]$ can be merged into a single value $v$.

#include <iostream>
#include <algorithm>

using namespace std;

int dp[60][270000];

void solve_large_merge() {
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int val; cin >> val;
        dp[val][i] = i + 1;
        ans = max(ans, val);
    }

    for (int v = 2; v < 60; ++v) {
        for (int i = 1; i <= n; ++i) {
            if (!dp[v][i] && dp[v-1][i] != 0) {
                dp[v][i] = dp[v-1][dp[v-1][i]];
            }
            if (dp[v][i]) ans = max(ans, v);
        }
    }
    cout << ans << endl;
}