HDU-1024 最大子段和分段问题

这道题要求将序列划分为 k 个连续子段，使得各段最大子段和的总和最大。直接暴力枚举显然无法承受数据规模，需要设计状态压缩的动态规划方案。

设 f[i][j] 表示前 j 个元素分成 i 段的最大和。转移时需要枚举上一段的分割点，导致复杂度爆炸。关键观察在于：转移过程中我们需要快速获取 max(f[i-1][k] + sum(k+1, j))，这可以通过维护前缀最优值来优化。

实际上，采用滚动数组压缩第一维，同时用一个辅助数组记录中间结果，就能将复杂度降到合理范围。具体地，g[j] 维护到当前位置为止的最优决策值，避免重复计算。

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

typedef long long ll;
const ll INF = (1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int seg, len;
    while (cin >> seg >> len) {
        vector<ll> val(len + 1);
        for (int i = 1; i <= len; i++) cin >> val[i];
        
        vector<ll> prev(len + 1, -INF), cur(len + 1, -INF);
        vector<ll> best(len + 1);
        
        for (int i = 0; i <= len; i++) best[i] = -INF;
        
        for (int k = 1; k <= seg; k++) {
            best[k - 1] = prev[k - 1];
            for (int j = k; j <= len; j++) {
                best[j] = max(best[j - 1], prev[j]);
                cur[j] = max(cur[j - 1] + val[j], best[j - 1] + val[j]);
            }
            swap(prev, cur);
            fill(cur.begin(), cur.end(), -INF);
        }
        
        ll res = -INF;
        for (int i = seg; i <= len; i++) 
            res = max(res, prev[i]);
        cout << res << "\n";
    }
    return 0;
}

HDU-1047 作业调度问题

给定 n 门课程及其截止时间和耗时，要求安排顺序使得总扣分最少。若完成时间超过截止期限，则产生延迟惩罚。数据范围 n ≤ 15 提示我们使用状态压缩动态规划。

每门课的完成状态用二进制位表示，dp[mask] 表示完成 mask 对应课程集合的最小扣分。对于状态 mask，枚举最后一门完成的课程 i，从 mask ^ (1 << i) 转移而来。

状态数仅 2^n，转移 O(n)，完全可行。为保证字典序最小，需按课程编号从小到大尝试，并在得分相同时保留编号更小的方案——但由于正向遍历自然满足字典序要求，只需在更新时严格取更优解即可。

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

struct Course {
    string name;
    int deadline, cost;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int cases;
    cin >> cases;
    while (cases--) {
        int n;
        cin >> n;
        vector<Course> crs(n);
        for (int i = 0; i < n; i++) 
            cin >> crs[i].name >> crs[i].deadline >> crs[i].cost;
        
        int total = 1 << n;
        vector<int> dp(total, INT_MAX);
        vector<int> spend(total, 0);
        vector<vector<int>> path(total);
        
        dp[0] = 0;
        
        for (int mask = 1; mask < total; mask++) {
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i))) continue;
                int pre = mask ^ (1 << i);
                int fin = spend[pre] + crs[i].cost;
                int penalty = max(0, fin - crs[i].deadline);
                
                if (dp[pre] + penalty < dp[mask]) {
                    dp[mask] = dp[pre] + penalty;
                    spend[mask] = fin;
                    path[mask] = path[pre];
                    path[mask].push_back(i);
                }
            }
        }
        
        cout << dp[total - 1] << "\n";
        for (int idx : path[total - 1]) 
            cout << crs[idx].name << "\n";
    }
    return 0;
}

状压 DP 的核心在于：将集合信息编码为整数位运算，把指数级搜索转化为多项式级别的状态转移。它与深度优先搜索的本质区别在于——搜索是"生成路径"，而 DP 是"复用子结构"。当所有子问题的最优解被记忆化后，整体最优解自然构建完成。