1. 0/1 背包问题的贪心预处理应用

在处理有限预算的购买问题时，若要求余额尽可能小，且最后一次购买不受预算限制（只要余额不少于 5 元），可以将问题转化为 0/1 背包。核心思路是保留 5 元用于购买价格最高的物品，其余 $m-5$ 的金额则作为背包容量，对前 $n-1$ 个较便宜的物品进行最大化填充。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int solve_knapsack() {
    int n, budget;
    while (cin >> n && n != 0) {
        vector<int> prices(n);
        for (int i = 0; i < n; ++i) cin >> prices[i];
        sort(prices.begin(), prices.end());
        cin >> budget;

        if (budget < 5) {
            cout << budget << endl;
            continue;
        }

        int limit = budget - 5;
        vector<int> dp(limit + 1, 0);
        
        // 使用前 n-1 个物品填充 limit 容量
        for (int i = 0; i < n - 1; ++i) {
            for (int j = limit; j >= prices[i]; --j) {
                dp[j] = max(dp[j], dp[j - prices[i]] + prices[i]);
            }
        }
        // 最终余额 = 总预算 - 已选物品总价 - 最大单价物品
        cout << budget - dp[limit] - prices[n - 1] << endl;
    }
    return 0;
}

2. 区间 DP：最小代价构造回文串

给定一个字符串，通过添加或删除字符将其变为回文串。由于增加一个字符和删除一个字符在效果上是等价的，我们只需为每个字符保留 min(add_cost, delete_cost)。定义 $dp[i][j]$ 为将区间 $[i, j]$ 变为回文串的最小代价。

状态转移方程：

• 若 $s[i] == s[j]$，则 $dp[i][j] = dp[i+1][j-1]$
• 否则，$dp[i][j] = \min(dp[i+1][j] + cost[s[i]], dp[i][j-1] + cost[s[j]])$

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int memo[2005][2005];
int char_cost[26];

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    for (int i = 0; i < n; ++i) {
        char c;
        int a, d;
        cin >> c >> a >> d;
        char_cost[c - 'a'] = min(a, d);
    }

    for (int len = 2; len <= m; ++len) {
        for (int i = 0; i <= m - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                memo[i][j] = (len == 2) ? 0 : memo[i + 1][j - 1];
            } else {
                memo[i][j] = min(memo[i + 1][j] + char_cost[s[i] - 'a'],
                                  memo[i][j - 1] + char_cost[s[j] - 'a']);
            }
        }
    }
    cout << memo[0][m - 1] << endl;
    return 0;
}

3. 状压 DP：多任务调度优化

在任务具有截止时间和扣分惩罚时，求最小扣分。当任务数量较少（$N \le 15$）时，可使用状态压缩 DP。$dp[mask]$ 表示完成集合 $mask$ 中任务的最小惩罚。为了满足字典序要求，在状态转移时逆序遍历任务。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Task {
    string title;
    int deadline, duration;
};

void solve() {
    int n;
    cin >> n;
    vector<Task> tasks(n);
    for (int i = 0; i < n; ++i) cin >> tasks[i].title >> tasks[i].deadline >> tasks[i].duration;

    int total_states = 1 << n;
    vector<int> dp(total_states, 1e9);
    vector<int> time_sum(total_states, 0);
    vector<int> parent(total_states, 0);
    vector<int> last_task(total_states, 0);

    dp[0] = 0;
    for (int mask = 0; mask < total_states; ++mask) {
        for (int i = 0; i < n; ++i) {
            if (!(mask & (1 << i))) {
                int next_mask = mask | (1 << i);
                time_sum[next_mask] = time_sum[mask] + tasks[i].duration;
                int penalty = max(0, time_sum[next_mask] - tasks[i].deadline);
                if (dp[mask] + penalty <= dp[next_mask]) {
                    dp[next_mask] = dp[mask] + penalty;
                    last_task[next_mask] = i;
                    parent[next_mask] = mask;
                }
            }
        }
    }

    cout << dp[total_states - 1] << endl;
    vector<string> res;
    int curr = total_states - 1;
    while (curr > 0) {
        res.push_back(tasks[last_task[curr]].title);
        curr = parent[curr];
    }
    for (int i = n - 1; i >= 0; --i) cout << res[i] << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

4. 斜率优化：序列分割代价最小化

对于序列分割问题，代价函数包含前缀和的平方项时，通常可以使用斜率优化将 $O(N^2)$ 的复杂度降至 $O(N)$。 方程形式：$dp[i] = \min(dp[j] + (sum[i] - sum[j])^2 + M)$。 展开并整理得：$dp[j] + sum[j]^2 = 2 \cdot sum[i] \cdot sum[j] + dp[i] - M - sum[i]^2$。 这符合直线方程 $y = kx + b$，其中 $y = dp[j] + sum[j]^2$，$x = sum[j]$，$k = 2 \cdot sum[i]$。

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

typedef long long ll;

ll get_y(int j, const vector<ll>& dp, const vector<ll>& s) {
    return dp[j] + s[j] * s[j];
}

void compute() {
    int n;
    ll m;
    while (cin >> n >> m) {
        vector<ll> s(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            ll val; cin >> val;
            s[i] = s[i - 1] + val;
        }

        vector<ll> dp(n + 1, 0);
        deque<int> q;
        q.push_back(0);

        for (int i = 1; i <= n; ++i) {
            while (q.size() >= 2) {
                int j1 = q[0], j2 = q[1];
                if (get_y(j2, dp, s) - get_y(j1, dp, s) <= 2 * s[i] * (s[j2] - s[j1])) {
                    q.pop_front();
                } else break;
            }

            int best_j = q.front();
            dp[i] = dp[best_j] + (s[i] - s[best_j]) * (s[i] - s[best_j]) + m;

            while (q.size() >= 2) {
                int j2 = q[q.size() - 2], j3 = q.back();
                if ((get_y(j3, dp, s) - get_y(j2, dp, s)) * (s[i] - s[j3]) >= 
                    (get_y(i, dp, s) - get_y(j3, dp, s)) * (s[j3] - s[j2])) {
                    q.pop_back();
                } else break;
            }
            q.push_back(i);
        }
        cout << dp[n] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    compute();
    return 0;
}