i got bored enough to port another solution from my gists lol
so yknow i was on the dp grind when someone posted this problem on the github issues for the usaco guide (you can test here, but prepare google translate)
so we have a buncha circles, intervals really
and we wanna remove some so that none of them intersect
(they can be tangent tho)
so let's define `min_remove[s][e]` as the minimum amount of circles we have to
remove given that the only circles we consider are the ones that are completely
in the interval `[s, e]`
the recurrence for this is as follows:
we go through all the middle cutting points and calculate the cost for isolating
the left & right parts completely from each other, which would mean removing
all circles in the interval that intersect with `mid`
NOTE however, that we don't include the
circle that goes completely around the entire interval,
because it doesn't interfere with the left & right parts
so if the cutting point was defined as `mid`, we'd have this:
``` min_remove[s][e] = min_remove[s][mid - 1] + min_remove[s][mid + 1] + circles_in[mid] ```so we just do a simple range dp with this relation and basically win the problem
right?
WRONG.
you see, the dp relation itself isn't hard- it's calculating `circles_in` that's the hard part (at least it was the case for me)
so to fix this, we need to define ANOTHER DP ARRAY
`circles_in[s][e][i]`
is going to be the number of circles that intersect the point
`s + i` given that the only circles we consider are in `[s, e]`
(excluding the possible outermost one that covers both `s` and `e`)
...actually, i think i'll leave it to the code to explain it
it does a better job
but enough rambling, here's the solution
```cpp #include <iostream> #include <vector> #include <algorithm> using std::cout; using std::endl; using std::vector; using std::pair; int main() { int circle_num; std::cin >> circle_num; // they're gonna be specified by start & end instead of center & radius vector<pair<int, int>> circles(circle_num); int min = INT32_MAX; // just gonna assume valid input lmao for (int c = 0; c < circle_num; c++) { int center; int radius; std::cin >> center >> radius; circles[c] = {center - radius, center + radius}; min = std::min(min, circles[c].first); } // normalize the intervals int max = INT32_MIN; for (int c = 0; c < circle_num; c++) { circles[c].first -= min; circles[c].second -= min; max = std::max(max, circles[c].second); } vector<vector<vector<int>>> circles_in(max + 1, vector<vector<int>>(max + 1)); // fancy meeting you here, this is the part where i calculate circles_in for (const pair<int, int>& c : circles) { // set our base cases circles_in[c.first][c.second] = vector<int>(c.second - c.first - 1, 1); } for (int len = 2; len <= max; len++) { for (int start = 0; start + len <= max; start++) { int end = start + len; if (circles_in[start][end].empty()) { circles_in[start][end] = vector<int>(len - 1); } vector<int>& curr = circles_in[start][end]; const vector<int>& lprev = circles_in[start][end - 1]; const vector<int>& rprev = circles_in[start + 1][end]; const vector<int>& mprev = circles_in[start + 1][end - 1]; if (len > 2) { curr.front() += lprev.front(); curr.back() += rprev.back(); for (int i = 1; i < curr.size() - 1; i++) { /* * add the ones contributed by the left & right, * then account for overcounting by subtracting the stuff * that's common to both (aka in the middle) */ curr[i] += lprev[i] + rprev[i - 1] - mprev[i - 1]; } } } } // excluse the outermost circles for each interval (if thereis one) for (const pair<int, int>& c : circles) { vector<int>& interval = circles_in[c.first][c.second]; for (int& i : interval) { i--; } } vector<vector<int>> min_removed(max + 1, vector<int>(max + 1, INT32_MAX)); // set up base cases for (int i = 0; i <= max; i++) { min_removed[i][i] = 0; if (i < max) { min_removed[i][i + 1] = 0; } } // just do our range dp & win for (int len = 2; len <= max; len++) { for (int start = 0; start + len <= max; start++) { int end = start + len; for (int mid = start + 1; mid < end; mid++) { int left = min_removed[start][mid]; int right = min_removed[mid][end]; min_removed[start][end] = std::min( min_removed[start][end], left + right + circles_in[start][end][mid - start - 1] ); } } } cout << min_removed[0][max] << endl; } ```