A. [POI2004] SZP

Description

Given a directed graph with cycles, where each node has exactly one outgoing edge (non-self-loop), select the maximum number of nodes such that every selected node has at least one immediate predecessor that is not selected.

Solution

Observe that each weakly connected component contains exactly one cycle. Reverse all edges so each component becomes a base ring tree (a tree with one extra edge forming a cycle). The whole graph becomes a forest of base ring trees.

For each component, break one edge on the cycle to obtain a tree. Perform a tree DP rooted at one endpoint of the removed edge. Then reattach the edge and update the answer by considering the root's state when the edge is used (a kind of rerooting).

The DP state is dp[x][0/1] meaning the maximum number of nodes selectable in the subtree rooted at x, when x is not selected (0) or selected (1). For any node, dp[x][1] is always greater than dp[x][0]. Let y be a child of x. Transitions:

\[dp[x][0] = \sum dp[y][1]\]

\[dp[x][1] = \sum dp[y][1] + \max_y (dp[y][0] - dp[y][1])\]

After computing the DP, a rerooting step accounts for the removed edge. We need the state when the root is not selected, which forces one of its children to be unselected. The code uses pre[x] to record which child becomes unselected when x is chosen. A second pass processes states in reverse topological order to propagate this information. Finally, for each cycle root, the answer is the best of its two possible states taking the removed edge into account. Due to memory constraints, we store only parent pointers and process nodes in topological order without building adjacency lists.

Code

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;

int nodeCount;
int dsuParent[MAXN];          // DSU array
int parent[MAXN];             // parent in reversed graph
int dpChoose[MAXN][2];        // dp[x][1]=selected, dp[x][0]=not selected
int minDiff[MAXN];            // best dp[child][0]-dp[child][1] for node x
int answer;
int outDegree[MAXN];          // original outdegree (for topological order)
int bestUnselected[MAXN];     // child that becomes unselected when node x is chosen
int markBlocked[MAXN];        // auxiliary flag
vector<int> cycleRoots;

int findSet(int u) {
    if (u == dsuParent[u]) return u;
    return dsuParent[u] = findSet(dsuParent[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> nodeCount;
    for (int i = 1; i <= nodeCount; i++) dsuParent[i] = i;

    for (int i = 1; i <= nodeCount; i++) {
        int nxt;
        cin >> nxt;
        parent[i] = nxt;   // reversed edge: from i to nxt
        if (findSet(i) == findSet(nxt)) {
            cycleRoots.push_back(i);
            markBlocked[nxt] = 1;  // mark to help later
        } else {
            dsuParent[i] = nxt;    // union
            outDegree[nxt]++;
        }
    }

    // outDegree now holds the in-degree of the reversed graph
    int *topo = new int[nodeCount + 1];
    {
        int q[MAXN];
        q[0] = 0;
        for (int i = 1; i <= nodeCount; i++)
            if (!outDegree[i]) q[++q[0]] = i;
        for (int i = 1; i <= q[0]; i++) {
            int cur = q[i];
            topo[i] = cur;
            int p = parent[cur];
            if (p == 0) continue;
            if (--outDegree[p] == 0)
                q[++q[0]] = p;
        }
    }

    fill(minDiff, minDiff + nodeCount + 1, 0x3f3f3f3f);
    for (int idx = 1; idx <= nodeCount; idx++) {
        int x = topo[idx];
        int p = parent[x];
        if (p == 0) continue;
        dpChoose[p][0] += dpChoose[x][1];
        dpChoose[p][1] += dpChoose[x][1];
        int diff = dpChoose[x][1] - dpChoose[x][0];
        if (minDiff[p] >= diff) {
            if (minDiff[p] == diff) {
                if (!markBlocked[x])
                    bestUnselected[p] = x;
            } else {
                minDiff[p] = diff;
                bestUnselected[p] = x;
            }
        }
    }

    memset(markBlocked, 0, sizeof(markBlocked));
    for (int idx = nodeCount; idx >= 1; idx--) {
        int x = topo[idx];
        if (find(cycleRoots.begin(), cycleRoots.end(), x) != cycleRoots.end() || outDegree[x] == 0) {
            markBlocked[x] = 0;
            continue;
        }
        if (!markBlocked[parent[x]] || (markBlocked[parent[x]] && bestUnselected[parent[x]] != x))
            markBlocked[x] = 1;
    }

    for (int root : cycleRoots) {
        int parentOfParent = parent[parent[root]];
        bool extra = (bestUnselected[parentOfParent] != parent[root] && !markBlocked[parent[root]]);
        answer += max(dpChoose[root][1], dpChoose[root][0] + extra);
    }

    cout << answer << "\n";
    delete[] topo;
    return 0;
}

B. New Year's Eve Party (Interval Covering)

Description

You are given an array of length n and m intervals. Each interval i requires atleast ci selected positions. Choose the minimum total number of positions to satisfy all intervals.

Solution

Sort intervals by left endpoint ascending (tie-break by right endpoint ascending). Sweep from the last interval to the first. For each interval, first use already covered positions inside it to satisfy ci, then greedily pick uncovered positions from left to right to fill the remaining requirement. This guarantees minimal total selections because later sweeps will reuse selections as much as possible.

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005, MAXM = 5005;
int N, M;
int covered[MAXN];
struct Interval { int L, R, need; } intervals[MAXM];

int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++)
        cin >> intervals[i].L >> intervals[i].R >> intervals[i].need;
    sort(intervals + 1, intervals + M + 1,
         [](const Interval &a, const Interval &b) {
             return a.L != b.L ? a.L < b.L : a.R < b.R;
         });

    int ans = 0;
    for (int i = M; i >= 1; i--) {
        int l = intervals[i].L, r = intervals[i].R, req = intervals[i].need;
        for (int j = r; j >= l && req; j--)
            if (covered[j]) req--;
        ans += req;
        for (int j = l; j <= r && req; j++)
            if (!covered[j]) {
                covered[j] = 1;
                req--;
            }
    }
    cout << ans << "\n";
    return 0;
}

C. Horse Racing (Tian Ji's Strategy)

Description

Given two arrays a and b of length n, pair each element of a with a distinct element of b. If ai > bi gain 200 silver coins; if equal, 0; if smaller, lose 200 coins. Maximize total coins.

Solution

Sort both arrays descending. Use dynamic programming: dp[i][j] means after considering the first i opponents (from b), you have used j of your strongest horses (from the front). The remaining i - j horses come from the weakest end. Transition either by matching the next strongest horse or the weakest horse for the current opponent, updating the score accordingly.

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, horseA[N], horseB[N];
int dp[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> horseA[i];
    for (int i = 1; i <= n; i++) cin >> horseB[i];
    sort(horseA + 1, horseA + n + 1, greater<int>());
    sort(horseB + 1, horseB + n + 1, greater<int>());
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int k = i - j;  // number taken from back
            // Use a strong horse (front)
            int scoreA = (horseA[j + 1] > horseB[i + 1]) ? 200 :
                         (horseA[j + 1] < horseB[i + 1]) ? -200 : 0;
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + scoreA);
            // Use a weak horse (back)
            int scoreB = (horseA[n - k] > horseB[i + 1]) ? 200 :
                         (horseA[n - k] < horseB[i + 1]) ? -200 : 0;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + scoreB);
        }
    }
    int ans = -1e9;
    for (int j = 0; j <= n; j++) ans = max(ans, dp[n][j]);
    cout << ans << "\n";
    return 0;
}

D. [APIO/CTSC2007] Data Backup

Description

There are n buildings on a number line. You may connect pairs of buildings, paying the distance between them. Each building can be connected at most once. You must make exactly K connections. Minimise total cost.

Solution

The optimal solution always connects adjacent buildings, so first compute the n-1 gaps gap[i] = pos[i] - pos[i-1]. The problem becomes choosing K gaps such that no two chosen gaps are adjacent, minimizing the sum.

DP with rolling array: dp[i][k] = minimum cost to select k gaps among the first i gaps, with the i-th gap selected. Transition: dp[i][k] = min_{j < i-1} dp[j][k-1] + gap[i]. Maintain a running prefix minimum from dp[i-2] for the previous layer.

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int N, K, gap[MAXN];
int dp[MAXN][2];

int main() {
    cin >> N >> K;
    int prev, cur;
    cin >> prev;
    for (int i = 2; i <= N; i++) {
        cin >> cur;
        gap[i - 1] = cur - prev;
        prev = cur;
    }
    N = N - 1;   // number of gaps
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = dp[0][1] = 0;

    for (int k = 1; k <= K; k++) {
        int bestPrev = 0x3f3f3f3f;
        for (int i = 2 * k; i <= N - (K - k) * 2; i++) {
            bestPrev = min(bestPrev, dp[i - 2][!(k & 1)]);
            dp[i][k & 1] = bestPrev + gap[i];
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 2 * K; i <= N; i++)
        ans = min(ans, dp[i][K & 1]);
    cout << ans << "\n";
    return 0;
}

E. [TJOI2013] Rescue the Dwarves

Description

Several dwarves fell into a trap of depth H. Each dwarf has body height (shoulder) Ai and arm length Bi. They can form a human pyramid: if a dwarf on top has total body height of dwarves below + own body + own arm ≥ H, he can escape and is removed from the pyramid. Maximise the number of escaping dwarves.

Solution

Sort dwarves by Ai + Bi ascending (if tie, by Ai, then Bi). The intuition is that those with smaller total need a taller base to escape, so they should leave earlier. DP: dp[i][j] = maximum escapes after processing first i dwarves, remaining body height (excluding arms) of dwarves still inside is j. Transition: either the dwarf stays (dp[i-1][j]) or escapes if possible (dp[i-1][j + A<sub>i</sub>] + 1). Use a rolling array over the height dimension.

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005, MAXH = 400005;
int n, H, totalBody;
int dp[2][MAXH * 2];          // offset by MAXH for safety
struct Dwarf {
    int body, arm;
    bool operator<(const Dwarf &o) const {
        if (body + arm != o.body + o.arm)
            return body + arm < o.body + o.arm;
        if (body != o.body) return body < o.body;
        return arm < o.arm;
    }
} dwarves[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> dwarves[i].body >> dwarves[i].arm;
        totalBody += dwarves[i].body;
    }
    sort(dwarves + 1, dwarves + n + 1);
    cin >> H;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dwarves[i].body + dwarves[i].arm >= H) {
            ans += n - i + 1;
            cout << ans << "\n";
            return 0;
        }
        memcpy(dp[i & 1], dp[!(i & 1)], sizeof dp[!(i & 1)]);
        int minHeight = H - dwarves[i].body - dwarves[i].arm + MAXH;
        for (int h = totalBody - dwarves[i].body + MAXH; h >= minHeight; h--) {
            dp[i & 1][h] = max(dp[!(i & 1)][h],
                               dp[!(i & 1)][h + dwarves[i].body] + 1);
            ans = max(ans, dp[i & 1][h]);
        }
    }
    cout << ans << "\n";
    return 0;
}