Maximizing Collected Value from Falling Objects
Given n falling objects on a 2D plane, each with a falling speed and initial height, starting from position (x0, 0). When directly aligned with an object, it can be collected instantly, yielding a value equal to its current height divided by 1000. The objective is to maximize the total collected value while gathering all objects.
Since collecting takes no time, passing an object implies it should be collected immediately. Thus, the set of collected objects always forms a contiguous interval, making Interval DP suitable.
Define dp_left[i][j] and dp_right[i][j] as the minimum total fallen distance by all uncollected objects after gathering the interval [i, j] and stopping at the left or right end, respectively. The penalty for movement is the sum of falling speeds of uncollected objects multiplied by the travel time. Prefix sums of falling speeds efficiently compute this penalty. The final answer equals the total initial heights minus the minimum penalty, all divided by 1000.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int obj_cnt, start_x;
int dp_left[MAXN][MAXN], dp_right[MAXN][MAXN];
int total_height = 0, rate_psum[MAXN];
struct Item {
int pos, height, rate;
} objects[MAXN];
bool cmpItems(const Item& a, const Item& b) { return a.pos < b.pos; }
int main() {
cin >> obj_cnt >> start_x;
for (int i = 1; i <= obj_cnt; i++) cin >> objects[i].pos;
for (int i = 1; i <= obj_cnt; i++) cin >> objects[i].height;
for (int i = 1; i <= obj_cnt; i++) cin >> objects[i].rate;
objects[++obj_cnt].pos = start_x;
objects[obj_cnt].height = 0;
objects[obj_cnt].rate = 0;
sort(objects + 1, objects + obj_cnt + 1, cmpItems);
memset(dp_left, 0x3f, sizeof dp_left);
memset(dp_right, 0x3f, sizeof dp_right);
for (int i = 1; i <= obj_cnt; i++) {
total_height += objects[i].height;
rate_psum[i] = rate_psum[i - 1] + objects[i].rate;
if (objects[i].pos == start_x && objects[i].height == 0 && objects[i].rate == 0) {
dp_left[i][i] = dp_right[i][i] = 0;
}
}
for (int len = 2; len <= obj_cnt; len++) {
for (int i = 1; i <= obj_cnt - len + 1; i++) {
int j = i + len - 1;
int unvisited = rate_psum[obj_cnt] - rate_psum[j] + rate_psum[i];
dp_left[i][j] = min(dp_left[i + 1][j] + (objects[i + 1].pos - objects[i].pos) * unvisited,
dp_right[i + 1][j] + (objects[j].pos - objects[i].pos) * unvisited);
int unvisited2 = rate_psum[obj_cnt] - rate_psum[j - 1] + rate_psum[i - 1];
dp_right[i][j] = min(dp_left[i][j - 1] + (objects[j].pos - objects[i].pos) * unvisited2,
dp_right[i][j - 1] + (objects[j].pos - objects[j - 1].pos) * unvisited2);
}
}
printf("%.3lf", (total_height - min(dp_left[1][obj_cnt], dp_right[1][obj_cnt])) / 1000.0);
return 0;
}
Minimum Steps to Uniform Array Transformation
An array can be modified by selecting a segment and replacing all its elements with a value not currently present in that segment. Find the minimum operations required to make the entire array consist of a single uniform value.
Interval DP is applied using two 3D arrays. match_dp[i][j][v] tracks the minimum steps to make segment [i, j] entirely equal to v, while avoid_dp[i][j][v] tracks the minimum steps to make [i, j] entirely NOT equal to v.
Transitions for avoid_dp involve merging two adjacent subsegments that both avoid v, or taking the minimum avoid_dp[i][j][w] (for w ≠ v) and adding 1 step to convert the result to avoiding v. For match_dp, transitions merge subsegments both matching v, or convert an avoidance state into a matching state by applying one operation (avoid_dp[i][j][v] + 1).
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;
int test_cases, arr_len, val_limit;
int vals[MAXN];
int match_dp[MAXN][MAXN][MAXN], avoid_dp[MAXN][MAXN][MAXN];
int main() {
cin >> test_cases;
while (test_cases--) {
cin >> arr_len >> val_limit;
memset(match_dp, 0x3f, sizeof match_dp);
memset(avoid_dp, 0x3f, sizeof avoid_dp);
for (int i = 1; i <= arr_len; i++) {
cin >> vals[i];
for (int j = 1; j <= val_limit; j++) {
match_dp[i][i][j] = (j != vals[i]);
avoid_dp[i][i][j] = (j == vals[i]);
}
}
for (int len = 1; len <= arr_len; len++) {
for (int i = 1; i <= arr_len - len + 1; i++) {
int j = i + len - 1;
int min_avoid = 0x3f3f3f3f;
for (int k = 1; k <= val_limit; k++) {
for (int m = i; m < j; m++)
avoid_dp[i][j][k] = min(avoid_dp[i][j][k], avoid_dp[i][m][k] + avoid_dp[m + 1][j][k]);
min_avoid = min(min_avoid, avoid_dp[i][j][k]);
}
for (int k = 1; k <= val_limit; k++)
avoid_dp[i][j][k] = min(avoid_dp[i][j][k], min_avoid + 1);
for (int k = 1; k <= val_limit; k++) {
for (int m = i; m < j; m++)
match_dp[i][j][k] = min(match_dp[i][j][k], match_dp[i][m][k] + match_dp[m + 1][j][k]);
match_dp[i][j][k] = min(match_dp[i][j][k], avoid_dp[i][j][k] + 1);
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 1; i <= val_limit; i++) ans = min(ans, match_dp[1][arr_len][i]);
cout << ans << "\n";
}
return 0;
}
Maximizing Remaining Length of Extinguished Candles
Given n candles at positions xi with initial lengths ai, burning at 1 unit per second. Starting at the origin and moving at 1 unit/sec, extinguishing is instantaneous. Maximize the total remaining length of all candles.
Visited candles form a contiguous interval. Tracking exact time t is infeasible due to large bounds; instead, track the number of currently burning candles k. stop_left[i][j][k] and stop_right[i][j][k] store the maximum remaining length after visiting [i, j] with k candles still burning, ending at the left or right end.
A dummy candle of length 0 is added at the origin. When moving to a candle, it either burned out before arrival (incurring a penalty of k × distance, adding 0 length) or was extinguished upon arrival (incurring (k+1) × distance penalty, but saving its initial length).
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 305;
int candle_cnt;
long long stop_left[MAXN][MAXN][MAXN], stop_right[MAXN][MAXN][MAXN];
struct Candle {
long long pos, init_len;
} candles[MAXN];
bool cmpCandles(const Candle& a, const Candle& b) { return a.pos < b.pos; }
int main() {
cin >> candle_cnt;
for (int i = 1; i <= candle_cnt; i++) {
cin >> candles[i].pos >> candles[i].init_len;
if (abs(candles[i].pos) >= candles[i].init_len) candles[i].init_len = 0;
}
candle_cnt++;
candles[candle_cnt].pos = 0;
candles[candle_cnt].init_len = 0;
sort(candles + 1, candles + candle_cnt + 1, cmpCandles);
for (int i = 1; i <= candle_cnt; i++)
for (int j = 1; j <= candle_cnt; j++)
for (int k = 0; k <= candle_cnt; k++)
stop_left[i][j][k] = stop_right[i][j][k] = -1e18;
for (int i = 1; i <= candle_cnt; i++) {
if (candles[i].pos == 0 && candles[i].init_len == 0) {
for (int k = 0; k < candle_cnt; k++)
stop_left[i][i][k] = stop_right[i][i][k] = 0;
break;
}
}
for (int len = 2; len <= candle_cnt; len++) {
for (int i = 1; i <= candle_cnt - len + 1; i++) {
int j = i + len - 1;
for (int k = 0; k <= candle_cnt - len; k++) {
long long d1 = candles[i + 1].pos - candles[i].pos;
long long d2 = candles[j].pos - candles[i].pos;
stop_left[i][j][k] = max(stop_left[i][j][k], stop_left[i + 1][j][k] - k * d1);
stop_left[i][j][k] = max(stop_left[i][j][k], stop_right[i + 1][j][k] - k * d2);
stop_left[i][j][k] = max(stop_left[i][j][k], candles[i].init_len + stop_left[i + 1][j][k + 1] - (k + 1) * d1);
stop_left[i][j][k] = max(stop_left[i][j][k], candles[i].init_len + stop_right[i + 1][j][k + 1] - (k + 1) * d2);
long long d3 = candles[j].pos - candles[j - 1].pos;
long long d4 = candles[j].pos - candles[i].pos;
stop_right[i][j][k] = max(stop_right[i][j][k], stop_right[i][j - 1][k] - k * d3);
stop_right[i][j][k] = max(stop_right[i][j][k], stop_left[i][j - 1][k] - k * d4);
stop_right[i][j][k] = max(stop_right[i][j][k], candles[j].init_len + stop_right[i][j - 1][k + 1] - (k + 1) * d3);
stop_right[i][j][k] = max(stop_right[i][j][k], candles[j].init_len + stop_left[i][j - 1][k + 1] - (k + 1) * d4);
}
}
}
cout << max(stop_left[1][candle_cnt][0], stop_right[1][candle_cnt][0]);
return 0;
}
Identifying Non-Critical Nodes in Tree Maximum Matching
For a given tree, count the nodes u whose removal (along with its edges) leaves a forest whose maximum matching size equals the original tree's maximum matching.
Compute the tree's maximum matching using Tree DP. match_states[u][0] denotes the maximum matching in the subtree of u where u is not matched with a child, and match_states[u][1] where u is matched. Then, apply Rerooting DP. Propagate the parent's matching contributions down to each child, dynamically updating the match_states. If the maximum matching size for the tree structure remaining after removing u matches the global maximum, u is a valid node.
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 200005;
int node_cnt;
long long match_states[MAXN][2];
bool traversed[MAXN];
long long max_match, valid_nodes;
long long subtree_sum[MAXN], best_diff[MAXN], second_diff[MAXN], best_child[MAXN], child_cnt[MAXN];
vector<int> adjacency[MAXN];
void initial_dfs(int x) {
best_diff[x] = second_diff[x] = -1e18;
if (adjacency[x].size() > 1 || x == 1) match_states[x][1] = 1;
if (adjacency[x].size() == 1 && x != 1) best_diff[x] = 0;
for (int y : adjacency[x]) {
if (traversed[y]) continue;
traversed[y] = true;
child_cnt[x]++; initial_dfs(y);
match_states[x][0] += match_states[y][1];
match_states[x][1] += match_states[y][1];
long long diff = match_states[y][0] - match_states[y][1];
if (diff > best_diff[x]) {
second_diff[x] = best_diff[x]; best_child[x] = y; best_diff[x] = diff;
} else if (diff > second_diff[x]) second_diff[x] = diff;
}
match_states[x][1] += best_diff[x];
}
void reroot_dfs(int x) {
for (int y : adjacency[x]) {
if (traversed[y]) continue;
traversed[y] = true;
subtree_sum[x] += max(match_states[y][0], match_states[y][1]);
long long orig0 = match_states[x][0], orig1 = match_states[x][1];
child_cnt[x]--; child_cnt[y]++; match_states[x][0] -= max(match_states[y][0], match_states[y][1]);
match_states[x][1] -= match_states[y][1] + (!child_cnt[x]);
if (best_child[x] == y) { match_states[x][1] -= best_diff[x]; if (child_cnt[x]) match_states[x][1] += second_diff[x]; }
subtree_sum[y] += max(match_states[x][0], match_states[x][1]);
match_states[y][0] += max(match_states[x][0], match_states[x][1]);
match_states[y][1] += match_states[x][1] + (child_cnt[y] == 1);
long long prev_best = best_diff[y];
long long diff = match_states[x][0] - match_states[x][1];
if (diff > best_diff[y]) { second_diff[y] = best_diff[y]; best_child[y] = x; best_diff[y] = diff; }
else if (diff > second_diff[y]) second_diff[y] = diff;
match_states[y][1] += best_diff[y] - prev_best;
reroot_dfs(y); child_cnt[x]++; child_cnt[y]--; match_states[x][0] = orig0; match_states[x][1] = orig1;
}
if (subtree_sum[x] == max_match) valid_nodes++; }
int main() {
cin >> node_cnt;
for (int i = 1; i < node_cnt; i++) { int u, v; cin >> u >> v; adjacency[u].push_back(v); adjacency[v].push_back(u); }
traversed[1] = true; initial_dfs(1); max_match = max(match_states[1][0], match_states[1][1]);
fill(traversed, traversed + MAXN, false); traversed[1] = true; reroot_dfs(1);
cout << valid_nodes;
return 0;
}
Switch Sequence for Target Light States via Spanning Tree DP
Given n lights at positions with states 0/1, and m switches where each flips states in a segment [l, r]. Find a sorted sequence of switches to turn all lights to 0, or output -1.
Flipping states is modeled using an XOR difference array. Flipping [l, r] toggles diff_arr[l] and diff_arr[r+1]. The target requires all diff_arr elements to be 0. Connect node l to node r+1 for each switch. Construct a spanning forest to avoid cycle constraints. DFS the forest: if a node has diff_arr[x] = 1, the edge to its parent must be used to flip it, recording the switch ID. If the root ends up with 1, it's impossible.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 200005;
int light_cnt, switch_cnt;
int diff_arr[MAXN], explored[MAXN], parent[MAXN];
vector<pair<int, int>> edges[MAXN];
vector<int> solution;
struct Light { int pos, state; } lights[MAXN];
bool cmpLights(const Light& a, const Light& b) { return a.pos < b.pos; }
int findParent(int x) { if (x == parent[x]) return x; return parent[x] = findParent(parent[x]); }
int findLeft(int x) { int l = 1, r = light_cnt, res = 1; while (l <= r) { int mid = (l + r) >> 1; if (lights[mid].pos < x) l = mid + 1; else r = mid - 1, res = mid; } return res; }
int findRight(int x) { int l = 1, r = light_cnt, res = light_cnt; while (l <= r) { int mid = (l + r) >> 1; if (lights[mid].pos > x) r = mid - 1; else l = mid + 1, res = mid; } return res; }
void dfs(int x) {
for (auto& p : edges[x]) {
int y = p.first;
if (explored[y]) continue;
explored[y] = true; dfs(y);
if (diff_arr[y]) { solution.push_back(p.second); diff_arr[y] = 0; diff_arr[x] ^= 1; }
}
}
int main() {
cin >> light_cnt >> switch_cnt;
for (int i = 1; i <= light_cnt; i++) cin >> lights[i].pos >> lights[i].state;
sort(lights + 1, lights + light_cnt + 1, cmpLights);
for (int i = 1; i <= light_cnt + 1; i++) { diff_arr[i] = (lights[i].state ^ lights[i - 1].state); parent[i] = i; }
for (int i = 1; i <= switch_cnt; i++) {
int l, r; cin >> l >> r; l = findLeft(l); r = findRight(r);
if (l > r) continue;
int ln = findParent(l), rn = findParent(r + 1);
if (ln == rn) continue;
parent[ln] = findParent(rn); edges[l].push_back({r + 1, i}); edges[r + 1].push_back({l, i});
}
for (int i = 1; i <= light_cnt + 1; i++) {
if (!explored[i]) { explored[i] = true; dfs(i); if (diff_arr[i] && i <= light_cnt) { cout << "-1"; return 0; } }
}
sort(solution.begin(), solution.end());
cout << solution.size() << "\n";
for (int out : solution) cout << out << " ";
return 0;
}
Minimizing Maximum Colors on Root-to-Leaf Paths in Tree Partitioning
Partition a tree into disjoint paths colored identically. A node can share a color with at most two children. Minimize the maximum number of colors on any root-to-leaf path.
Binary search on the color limit K. Tree DP checks feasibility. color_dp[u][0], color_dp[u][1], color_dp[u][2] store the minimum maximum colors in the subtree of u if u shares its color with 0, 1, or 2 children. Extending an existing path doesn't increase color count; starting a new path adds 1. Transitions ensure path limits do not exceed K.
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 200005;
int tree_size;
int color_dp[MAXN][3];
bool seen[MAXN];
vector<int> tree_adj[MAXN];
void dfs(int x, int limit) {
color_dp[x][0] = color_dp[x][1] = color_dp[x][2] = 0;
for (int y : tree_adj[x]) {
if (seen[y]) continue; seen[y] = true; dfs(y, limit);
int new0 = 1e9, new1 = 1e9, new2 = 1e9;
if (color_dp[x][0] + color_dp[y][1] < limit) new1 = min(new1, max(color_dp[x][0], color_dp[y][1]));
if (color_dp[x][1] + color_dp[y][1] < limit) new2 = min(new2, max(color_dp[x][1], color_dp[y][1]));
if (color_dp[x][0] + color_dp[y][2] + 1 < limit) new0 = min(new0, max(color_dp[x][0], color_dp[y][2] + 1));
if (color_dp[x][1] + color_dp[y][2] + 1 < limit) new1 = min(new1, max(color_dp[x][1], color_dp[y][2] + 1));
if (color_dp[x][2] + color_dp[y][2] + 1 < limit) new2 = min(new2, max(color_dp[x][2], color_dp[y][2] + 1));
color_dp[x][0] = new0; color_dp[x][1] = new1; color_dp[x][2] = new2;
color_dp[x][1] = min(color_dp[x][1], color_dp[x][0]); color_dp[x][2] = min(color_dp[x][2], color_dp[x][1]);
}
}
bool check(int mid) { fill(seen, seen + MAXN, false); seen[1] = true; dfs(1, mid); return color_dp[1][2] <= mid; }
int main() {
cin >> tree_size;
for (int i = 1; i < tree_size; i++) { int a, b; cin >> a >> b; tree_adj[a].push_back(b); tree_adj[b].push_back(a); }
int l = 1, r = tree_size, ans = tree_size;
while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) r = mid - 1, ans = mid; else l = mid + 1; }
cout << ans;
return 0;
}
Minimum Cost Array Transformation via Segments and Reordering
Transform array A to B (length ≤ 22). Operations: change Ai to any value with cost |new - Ai|, or partition A into x segments and reorder them with cost c(×(x-1)). Minimize total cost.
Bitmask DP is applied. state_dp[mask] represents the minimum cost to match the first popcount(mask) elements of B using elements of A indicated by mask. To transition, select an unused element in A to start a new segment, continuously adding subsequent unused elements, matching them to the next positions in B, accumulating modification costs and adding the segment penalty c.
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 22;
int seq_len;
long long source_seq[MAXN + 1], target_seq[MAXN + 1], segment_cost;
long long state_dp[1 << MAXN];
int main() {
cin >> seq_len >> segment_cost;
for (int i = 1; i <= seq_len; i++) cin >> source_seq[i];
for (int i = 1; i <= seq_len; i++) cin >> target_seq[i];
memset(state_dp, 0x3f, sizeof state_dp);
state_dp[0] = -segment_cost;
for (int s = 0; s < (1 << seq_len); s++) {
int cnt = 0;
for (int t = s; t; t -= (t & -t)) cnt++;
for (int i = 1; i <= seq_len; i++) {
if (s & (1 << (i - 1))) continue;
int t = s; long long num = segment_cost;
for (int j = i; !(s & (1 << (j - 1))) && j <= seq_len; j++) {
t |= (1 << (j - 1)); num += abs(source_seq[j] - target_seq[cnt + j - i + 1]);
state_dp[t] = min(state_dp[t], state_dp[s] + num);
}
}
}
cout << state_dp[(1 << seq_len) - 1];
return 0;
}
Counting Valid Matrices with Prefix Monotonic Constraints
Starting with an n×m (≤ 18) zero matrix, an operation sets a prefix of a row or column to 1. A matrix is valid if obtainable. Given a 01? matrix, count valid completions modulo 998244353.
A valid matrix requires every 1 to have another 1 above it or to its left, or be at an edge. Bitmask DP tracks column states. ways_dp[r][c][col_mask][row_active] counts ways to fill up to row r, column c, where col_mask indicates if columns are fully filled with 1s, and row_active tracks if the current row prefix is filled. A cell can be 0 only if clearing the column fill status. It can be 1 if it continues an active row/column fill or initiates a new fill segment.
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 18;
const int MOD = 998244353;
int row_cnt, col_cnt;
int ways_dp[MAXN + 1][MAXN + 1][1 << MAXN][2];
char grid_chars[MAXN + 1][MAXN + 1];
int main() {
cin >> row_cnt >> col_cnt;
for (int i = 1; i <= col_cnt; i++) grid_chars[0][i] = '1';
for (int i = 1; i <= row_cnt; i++) for (int j = 1; j <= col_cnt; j++) cin >> grid_chars[i][j];
for (int i = 2; i <= row_cnt; i++) for (int j = 2; j <= col_cnt; j++) if (grid_chars[i][j] == '1' && grid_chars[i - 1][j] == '0' && grid_chars[i][j - 1] == '0') { cout << 0; return 0; }
if (grid_chars[1][1] != '0') ways_dp[1][1][(1 << col_cnt) - 1][1] = 1;
if (grid_chars[1][1] != '1') ways_dp[1][1][(1 << col_cnt) - 1][0] = 1;
for (int i = 1; i <= row_cnt; i++) {
for (int j = 1; j <= col_cnt; j++) {
if (i == row_cnt && j == col_cnt) break;
for (int s = 0; s < (1 << col_cnt); s++) {
for (int k = 0; k < 2; k++) {
int next_r = i, next_c = j + 1;
if (next_c > col_cnt) { next_r = i + 1; next_c = 1; }
if (grid_chars[next_r][next_c] != '1') (ways_dp[next_r][next_c][s & (~(1 << (next_c - 1)))][0] += ways_dp[i][j][s][k]) %= MOD;
if (grid_chars[next_r][next_c] != '0' && (k || (s & (1 << (next_c - 1))) || next_c == 1)) {
if (next_c > 1) (ways_dp[next_r][next_c][s][k] += ways_dp[i][j][s][k]) %= MOD;
else (ways_dp[next_r][next_c][s][1] += ways_dp[i][j][s][k]) %= MOD;
}
}
}
}
}
int ans = 0;
for (int s = 0; s < (1 << col_cnt); s++) (ans += (ways_dp[row_cnt][col_cnt][s][0] + ways_dp[row_cnt][col_cnt][s][1]) % MOD) %= MOD;
cout << ans;
return 0;
}
XOR Sum of Valid Word Counts Over Vowel Subsets Using SOS DP
Given n words of length 3, a vowel subset is chosen from 'a'-'x'. A word is valid if it contains at least one vowel. Find the XOR sum of (valid words count)2 over all 224 subsets.
Tracking words containing ≥1 vowel directly requires complex inclusion-exclusion. Instead, count words that contain no vowels. A word fails if all its letters are excluded from the vowel set. subset_freq[mask] counts words whose letters are entirely within mask (containing no letters outside mask). Sum Over Subsets (SOS) DP computes subset_freq[mask] by aggregating frequencies of all submasks. The number of valid words for a vowel set S is word_cnt - subset_freq[complement of S].
#include <iostream>
#include <string>
using namespace std;
int word_cnt;
long long subset_freq[1 << 24];
int main() {
cin >> word_cnt;
for (int i = 1; i <= word_cnt; i++) {
string w; cin >> w;
int mask = (1 << (w[0] - 'a')) | (1 << (w[1] - 'a')) | (1 << (w[2] - 'a'));
subset_freq[mask]++;
}
for (int i = 0; i < 24; i++) for (int s = 0; s < (1 << 24); s++) if (s & (1 << i)) subset_freq[s] += subset_freq[s ^ (1 << i)];
long long xor_sum = 0;
for (int s = 0; s < (1 << 24); s++) xor_sum ^= (word_cnt - subset_freq[s]) * (word_cnt - subset_freq[s]);
cout << xor_sum;
return 0;
}