Connected Component DP
Connected Component DP
JOI 2016 — Skyscraper
Problem Statement
Given , count the number of permutations of these numbers such that
Connected Component DP
Given , count the number of permutations of these numbers such that
where is a given integer.
Sort the array and insert elements in increasing order.
We build the permutation by value order, not by position.
While inserting elements, we track how many connected components of filled positions currently exist.
Example of a partial permutation: 1, 2, ?, ?, 3, ?, 5, ?
Here:
[1,2], [3], [5] → 3 componentsThis perspective allows us to reason about how inserting the next value changes both structure and cost.
Let
be the number of ways after inserting the first smallest elements such that:
? are equal to )When inserting , we consider all structural effects on components:
These actions change:
A key trick is how we maintain cost efficiently during incremental insertion.
Before inserting , all empty positions (?) are assumed to have value .
Since values are inserted in sorted order, this gives the minimum possible cost consistent with current structure.
When is actually inserted, all optimistic values become real.
Every adjacency involving ? increases by
So total cost increases by
Each connected component contributes two boundary edges. Filled ends remove one boundary each.
So:
Therefore:
From state after cost update:
Merge two components
Attach inside a component
Create new component
Create new end (if )
Extend to end (if )
int solve(int idx, int components, int cost, int filled_ends) {
if (filled_ends > 2 || cost > L) return 0;
if (components == 0 && idx > 1) return 0;
if (idx == n + 1) return filled_ends == 2 && components == 1;
int &ret = dp[idx][components][cost][filled_ends];
if (ret != -1) return ret;
int new_cost = cost + (a[idx] - a[idx - 1]) * (2 * components - filled_ends);
long long ans = 0;
if (components >= 2)
ans += (components - 1) *
solve(idx + 1, components - 1, new_cost, filled_ends);
if (components >= 1)
ans += (2 * components - filled_ends) *
solve(idx + 1, components, new_cost, filled_ends);
ans += (components + 1 - filled_ends) *
solve(idx + 1, components + 1, new_cost, filled_ends);
if (filled_ends < 2) {
ans += (2 - filled_ends) *
solve(idx + 1, components + 1, new_cost, filled_ends + 1);
ans += (2 - filled_ends) *
solve(idx + 1, components, new_cost, filled_ends + 1);
}
return ret = ans;
}