Progress: Dynamic Programming - Linear DP, Knapsack, Interval DP
Merging Palindromic Substrings
Tags: Interval DP
Foundation - Longest Palindromic Substring
Problem: Given a string (S), find the length of its longest palindromic substring.
Approach: A longer palindrome can always be constructed by adding identical characters to both ends of a smaller palindrome. Define (dp_{i,j}) as whether substring (S_{i,\dots,j}) is a palindrome. When (S_i = S_j), we have (dp_{i,j} |= dp_{i+1,j-1}). Handle substrings of length 1 and 2 as base cases.
Problem Solution
Building on the foundation, define (dp_{i,j,k,l}) to represent whether the string formed by merging (A_{i,\dots,j}) and (B_{k,\dots,l}) is a palindrome. Derive transitions analogously.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 55;
char strX[MAX], strY[MAX];
int memo[MAX][MAX][MAX][MAX];
int testCases, result;
int main() {
scanf("%d", &testCases);
int lenX, lenY;
while (testCases--) {
result = 0;
cin >> strX + 1 >> strY + 1;
lenX = strlen(strX + 1), lenY = strlen(strY + 1);
memset(memo, 0, sizeof(memo));
for (int szX = 0; szX <= lenX; szX++) {
for (int szY = 0; szY <= lenY; szY++) {
for (int i = 1; i + szX - 1 <= lenX; i++) {
for (int k = 1; k + szY - 1 <= lenY; k++) {
int j = i + szX - 1;
int p = k + szY - 1;
if (szX + szY <= 1) {
memo[i][j][k][p] = 1;
} else {
if (strX[i] == strX[j])
memo[i][j][k][p] |= memo[i + 1][j - 1][k][p];
if (strX[i] == strY[p])
memo[i][j][k][p] |= memo[i + 1][j][k][p - 1];
if (strY[k] == strY[p])
memo[i][j][k][p] |= memo[i][j][k + 1][p - 1];
if (strX[j] == strY[k])
memo[i][j][k][p] |= memo[i][j - 1][k + 1][p];
}
if (memo[i][j][k][p])
result = max(result, szX + szY);
}
}
}
}
printf("%d\n", result);
}
return 0;
}
Number Picking Game II
Tags: Interval DP
Approach: At each stage, the sequence A transitions by removing elements from either end. Define (dp_{l,r}) as the maximum (\sum v) achievable after removing (l) elements from the left and (r) elements from the right.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;
int cases, size, arrA[MAX], arrB[MAX];
int memo[MAX][MAX], best;
int main() {
scanf("%d", &cases);
while (cases--) {
best = -1;
memset(memo, 0, sizeof(memo));
scanf("%d", &size);
for (int i = 1; i <= size; i++)
scanf("%d", &arrA[i]);
for (int j = 1; j <= size; j++)
scanf("%d", &arrB[j]);
for (int i = 1; i <= size; i++) {
for (int left = 0; left <= i; left++) {
int right = i - left;
if (left == 0)
memo[0][right] = memo[0][right - 1] + arrB[i] * arrA[size - right + 1];
if (right == 0)
memo[left][0] = memo[left - 1][0] + arrB[i] * arrA[left];
else
memo[left][right] = max(memo[left - 1][right] + arrB[i] * arrA[left],
memo[left][right - 1] + arrB[i] * arrA[size - right + 1]);
best = max(best, memo[left][right]);
}
}
printf("%d\n", best);
}
return 0;
}
Street Lamp Problem
Tags: Interval DP
Approahc: When traveling from lamp (i) to lamp (j), lamps between them are automatically turned off. Define (dp_{i,j,0/1}) as the minimum power consumption to turn off lamps (i,\dots,j) when ending at the left/right end. The key insight is that transitions involve movement distance between lamps, not just lamp positions, since lamps may not form a continuous interval at a specific position D. When movement is negative, it represents returning to handle lamps that should have been automatically turned off.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 1010;
const long long INF = 1e16;
int lamps, velocity, position[MAX], weight[MAX];
long long prefixWeight[MAX], memo[MAX][MAX][2];
int main() {
while (cin >> lamps) {
scanf("%d", &velocity);
for (int i = 1; i <= lamps; i++)
scanf("%d %d", &position[i], &weight[i]),
prefixWeight[i] = prefixWeight[i - 1] + weight[i];
memset(memo, 0x3f, sizeof(memo));
memo[velocity][velocity][0] = 0;
memo[velocity][velocity][1] = 0;
for (int range = 2; range <= lamps; range++) {
for (int i = 1; i + range - 1 <= lamps; i++) {
int j = i + range - 1;
memo[i][j][0] = min(
memo[i + 1][j][0] + 1LL * (position[i + 1] - position[i]) *
(prefixWeight[lamps] - prefixWeight[j] + prefixWeight[i]),
memo[i + 1][j][1] + 1LL * (position[j] - position[i]) *
(prefixWeight[lamps] - prefixWeight[j] + prefixWeight[i])
);
memo[i][j][1] = min(
memo[i][j - 1][1] + 1LL * (position[j] - position[j - 1]) *
(prefixWeight[lamps] - prefixWeight[j - 1] + prefixWeight[i - 1]),
memo[i][j - 1][0] + 1LL * (position[j] - position[i]) *
(prefixWeight[lamps] - prefixWeight[j - 1] + prefixWeight[i - 1])
);
}
}
printf("%lld\n", min(memo[1][lamps][0], memo[1][lamps][1]));
}
return 0;
}
Matrix Number Picking Game
Tags: Interval DP High Precision
Note: High precision arithmetic is error-prone and time-consuming. For competitions with different time/memory limits per language, Python provides a practical alternative for handling large numbers.
rows, cols = [int(x) for x in input().split()]
matrix = []
for _ in range(rows):
matrix.append([int(x) for x in input().split()])
total = 0
for i in range(rows):
dp = [[0 for _ in range(cols)] for _ in range(cols)]
for length in range(cols - 1, 0, -1):
for left in range(cols - length + 1):
right = left + length - 1
if left > 0 and right == cols - 1:
dp[left][right] = dp[left - 1][right] + matrix[i][left - 1] * (2 ** (cols - length))
if left == 0 and right < cols - 1:
dp[left][right] = dp[left][right + 1] + matrix[i][right + 1] * (2 ** (cols - length))
elif left > 0 and right < cols - 1:
dp[left][right] = max(
dp[left][right + 1] + matrix[i][right + 1] * (2 ** (cols - length)),
dp[left - 1][right] + matrix[i][left - 1] * (2 ** (cols - length))
)
total += max([dp[j][j] + matrix[i][j] * (2 ** cols) for j in range(cols)])
print(total)
River Crossing During Migration
Tags: Greedy Sorting Order-Dependent Linear DP
Apporach: Following a greedy strategy, letting two slower people row to the opposite shore while the faster person returns may minimize total time. Since crossing time is determined by the slower person, those with longer times inevitably contribute to total time. Sort times as (T_1 \le T_2 \dots \le T_n). Based on this, two methods turn the current shore sequence into (T_1, T_2, \dots, T_{n-2}):
- Method A: Send 1 and 2 across, 1 returns, n-1 and n cross, 2 returns
- Method B: 1 carries n across, returns, carries n-1 across
These two methods can be proven optimal, enabling recursive computation.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100010;
int people, crossing[MAX], dp[MAX];
int main() {
scanf("%d", &people);
for (int i = 1; i <= people; i++)
scanf("%d", &crossing[i]);
sort(crossing + 1, crossing + people + 1);
dp[1] = crossing[1], dp[2] = crossing[2];
dp[3] = crossing[1] + crossing[2] + crossing[3];
for (int i = 4; i <= people; i++)
dp[i] = min(
dp[i - 2] + 2 * crossing[1] + crossing[i - 1] + crossing[i],
dp[i - 2] + 2 * crossing[2] + crossing[1] + crossing[i]
);
printf("%d", dp[people]);
}
Small A's Palindrome
Tags: Interval DP String
Approach: Drawing from the stone merging problem, append the original string to itself to handle circular cases.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 5010;
char text[MAX << 1];
int memo[MAX << 1][MAX << 1], longest = 1;
int main() {
cin >> text + 1;
int len = strlen(text + 1);
for (int i = 1; i <= len; i++)
text[len + i] = text[i];
for (int i = 1; i < 2 * len; i++)
memo[i][i] = 1;
for (int i = 1; i < 2 * len - 1; i++)
if (text[i] == text[i + 1])
memo[i][i + 1] = 1;
for (int sz = 3; sz <= len; sz++) {
for (int left = 1; left + sz - 1 <= 2 * len - 1; left++) {
int right = left + sz - 1;
if (text[left] == text[right])
memo[left][right] |= memo[left + 1][right - 1];
if (memo[left][right])
longest = max(longest, right - left + 1);
}
}
printf("%d", longest);
}
Simple Brute Force Problem
Tags: bitset
bitset Introduction
Approach: Use bitset for time optimization and rolling array for space optimization.
Time complexity: (\mathcal{O}(\frac{10^6 \cdot n \cdot (R-L)}{w})) where (w = 32).
#include <bits/stdc++.h>
using namespace std;
const int LIMIT = 1000001;
bitset<LIMIT> state[2], emptySet;
int sequences, leftBound[105], rightBound[105];
int main() {
scanf("%d", &sequences);
for (int i = 1; i <= sequences; i++)
scanf("%d %d", &leftBound[i], &rightBound[i]);
for (int val = leftBound[1]; val <= rightBound[1]; val++)
state[0][val * val] = 1;
for (int i = 2; i <= sequences; i++) {
for (int val = leftBound[i]; val <= rightBound[i]; val++)
state[1] |= state[0] << (val * val);
state[0] = state[1];
state[1] = emptySet;
}
printf("%d", (int)state[0].count());
return 0;
}