Dynamic Programming: 0/1 Knapsack Problem

This problem is a classic 0/1 knapsack implementation. The approach involves using dynamic programming where dp[j] represents the number of ways to order food items with exactly j yuan remaining. The recurrence relation is dp[j] = dp[j] + dp[j - a[i]], which means the original number of ways to have j yuan plus the ways to reach j by including the current dish that costs a[i]. The base case is dp[0] = 1, representing one way to spend zero yuan.

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> dishes(n);
    vector<ll> dp(m + 1);
    
    for (int i = 0; i < n; i++)
        cin >> dishes[i];

    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = m; j >= dishes[i]; j--) {
            dp[j] += dp[j - dishes[i]];
        }
    }
    
    cout << dp[m] << endl;

    return 0;
}

Climbing Stairs Problem

This problem is similar to the knapsack problem but with a different context. Here, dp[i] represents the number of distinct ways to reach the i-th step. Since you can climb 1 to K steps at a time, the first K steps can all be reached in one way. For steps beyond K, the reucrrence relation is dp[i] = dp[i] + dp[i-j], meaning the ways to reach step i include all ways to reach step i-j and then take j steps.

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MOD = 100003;
    int steps, max_step;
    cin >> steps >> max_step;
    
    vector<ll> dp(steps + 1, 0);
    for(int i = 1; i <= max_step; i++)
        dp[i] = 1;
    
    for(int i = 2; i <= steps; i++) {
        for(int j = 1; j <= max_step && i - j >= 0; j++) {
            dp[i] = (dp[i] % MOD + dp[i - j] % MOD) % MOD;
        }
    }

    cout << dp[steps] << '\n';

    return 0;
}

Visibility Check Using GCD

Initially, this problem might seem to require checking all eight directions, but further analysis reveals that a hunter can see a rabbit if the line connecting them doesn't pass through any other integer points. This occurs when the greatest common divisor (GCD) of the absolute differences in their coordinates is 1. For C++14, we can use the built-in __gcd function, while C++17 provides std::gcd in the <numeric> header.

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_cases;
    cin >> test_cases;
    while(test_cases--) {
        int rabbit_x, rabbit_y, hunter_x, hunter_y;
        cin >> rabbit_x >> rabbit_y >> hunter_x >> hunter_y;

        bool visible = true;
        if(__gcd(abs(rabbit_x - hunter_x), abs(rabbit_y - hunter_y)) == 1) 
            visible = false;

        cout << (visible ? "yes" : "no") << '\n';
    }

    return 0;
}

Sequence Segmentation

This problem requires segmenting a sequence such that the sum of elements in each segment does not exceed a given threshold M. The approach involves iterating through the sequence from left to right, accumulating values until adding the next element would exceed M, at which point a new segment is started. The count of segments is then returned.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> sequence(n);
    for(auto &num : sequence) cin >> num;

    int current_sum = 0, segments = 1;
    for(int i = 0; i < n; i++) {
        if(current_sum + sequence[i] <= m) {
            current_sum += sequence[i];
        } else {
            current_sum = sequence[i];
            segments++;
        }
    }

    cout << segments << '\n';

    return 0;
}

Optimal Hospital Placement

This problem involves finding the optimal location for a hospital in a tree-structured area such that the total weighted distance from all nodes is minimized. Each node has a population weight. The solution involves calcluating the total weighted distance for each node as the potential hospital location and selecting the one with the minimum value. This is done using a depth-first search (DFS) traversal to compute distances.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int locations;
    cin >> locations;
    vector<int> population(locations + 1);
    vector<vector<int>> graph(locations + 1);
    
    for(int i = 1; i <= locations; i++) {
        int left, right;
        cin >> population[i] >> left >> right;
        graph[i].push_back(left);
        graph[i].push_back(right);
        graph[left].push_back(i);
        graph[right].push_back(i);
    }

    ll min_total = LLONG_MAX;
    
    auto calculate_distance = [&](auto self, int node, int parent, int distance) -> void {
        if(!node) return;
        
        for(auto neighbor : graph[node]) {
            if(neighbor == parent) continue;
            self(self, neighbor, node, distance + 1);
            population[node] += population[neighbor];
        }
    };

    for(int i = 1; i <= locations; i++) {
        vector<int> temp_pop = population;
        ll total_distance = 0;
        
        auto dfs = [&](auto self, int node, int parent, int distance) -> void {
            if(!node) return;
            
            for(auto neighbor : graph[node]) {
                if(neighbor == parent) continue;
                self(self, neighbor, node, distance + 1);
                total_distance += temp_pop[neighbor] * distance;
            }
        };
        
        dfs(dfs, i, 0, 1);
        min_total = min(min_total, total_distance);
    }

    cout << min_total << '\n';

    return 0;
}