Bailian / 动态规划与贪心

DP / 贪心题解整理

这份页面根据你批量下载的题面整理，覆盖 25 道题。每题都给出基本思路、可交的标准代码和易错提醒，适合作为刷题记录页或个人网站专题页。

总题数：25
主题：贪心 / DP
用途：训练记录 / 复盘 / 网站展示

贪心

1017 装箱问题贪心绿先做

题目链接

基本思路

按箱子大小从大到小贪心装。6x6、5x5、4x4、3x3 先各自占掉若干大箱子，再利用这些箱子里的剩余空间去补 2x2 和 1x1。最后再处理剩余的 2x2 和 1x1。

标准代码

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

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

    while (true) {
        int a[7];
        for (int i = 1; i <= 6; ++i) cin >> a[i];
        if (!a[1] && !a[2] && !a[3] && !a[4] && !a[5] && !a[6]) break;

        int ans = 0;
        ans += a[6];

        ans += a[5];
        a[1] = max(0, a[1] - 11 * a[5]);

        ans += a[4];
        int need2 = 5 * a[4];
        if (a[2] >= need2) a[2] -= need2;
        else {
            int lack = need2 - a[2];
            a[1] = max(0, a[1] - lack * 4);
            a[2] = 0;
        }

        ans += (a[3] + 3) / 4;
        int rem3 = a[3] % 4;
        if (rem3) {
            static int need2arr[4] = {0, 5, 3, 1};
            static int need1arr[4] = {0, 7, 6, 5};
            int need2 = need2arr[rem3];
            if (a[2] >= need2) {
                a[2] -= need2;
                a[1] = max(0, a[1] - need1arr[rem3] * 4);
            } else {
                int lack = need2 - a[2];
                a[1] = max(0, a[1] - need1arr[rem3] * 4 - lack * 4);
                a[2] = 0;
            }
        }

        if (a[2] > 0) {
            ans += (a[2] + 8) / 9;
            int rem2 = a[2] % 9;
            if (rem2) a[1] = max(0, a[1] - (36 - rem2 * 4));
        }

        if (a[1] > 0) ans += (a[1] + 35) / 36;

        cout << ans << '\n';
    }
    return 0;
}

易错提醒

3x3 剩余 1、2、3 块时，补空间的公式不一样，别写混。
补 2x2 不够时，要把缺的部分换算成 1x1。
所有扣减都要注意别减成负数。

1065 Wooden Sticks 贪心黄进阶

题目链接

基本思路

先按长度升序、长度相同按重量升序排序。然后反复从前往后贪心选一条“可接上的链”，把能接上的木棍都拿掉，一共要开多少条链就是答案。

标准代码

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

struct Stick {
    int l, w;
    bool used = false;
};

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<Stick> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i].l >> a[i].w;
        sort(a.begin(), a.end(), [](const Stick& x, const Stick& y) {
            if (x.l != y.l) return x.l < y.l;
            return x.w < y.w;
        });

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i].used) continue;
            ++ans;
            a[i].used = true;
            int lastw = a[i].w;
            for (int j = i + 1; j < n; ++j) {
                if (!a[j].used && a[j].w >= lastw) {
                    a[j].used = true;
                    lastw = a[j].w;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

易错提醒

排序时长度相同必须按重量升序，否则贪心链会出错。
这是“最少链覆盖”，不是普通 LIS。
题目多组数据，`used` 每组都要重置。

1083 Moving Tables 贪心绿先做

题目链接

基本思路

把房间号映射成走廊段编号：`(room + 1) / 2`。每次搬桌子占用的是一个闭区间，统计每个走廊段被多少次搬运覆盖，最大覆盖次数乘 10 就是答案。

标准代码

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> cnt(205, 0);
        for (int i = 0; i < n; ++i) {
            int s, t;
            cin >> s >> t;
            s = (s + 1) / 2;
            t = (t + 1) / 2;
            if (s > t) swap(s, t);
            for (int j = s; j <= t; ++j) cnt[j]++;
        }
        int mx = *max_element(cnt.begin(), cnt.end());
        cout << mx * 10 << '\n';
    }
    return 0;
}

易错提醒

房间要先映射到走廊段，不是直接拿原编号做区间。
端点重合算冲突，所以要按闭区间统计。
答案单位是分钟，最后别忘记乘 10。

1328 Radar Installation 贪心黄进阶

题目链接

基本思路

每个岛 `(x, y)` 能被雷达覆盖，当且仅当雷达放在区间 `[x - sqrt(d^2-y^2), x + sqrt(d^2-y^2)]` 内。于是问题变成最少选几个点覆盖所有区间，按右端点排序后贪心选点。

标准代码

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

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

    int n, d, tc = 1;
    while (cin >> n >> d, n || d) {
        vector<pair<double, double>> segs;
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            if (y > d) ok = false;
            else {
                double dx = sqrt(1.0 * d * d - 1.0 * y * y);
                segs.push_back({x - dx, x + dx});
            }
        }
        if (!ok) {
            cout << "Case " << tc++ << ": -1\n";
            continue;
        }
        sort(segs.begin(), segs.end(), [](auto& a, auto& b) {
            return a.second < b.second;
        });
        int ans = 0;
        double last = -1e100;
        for (auto& [l, r] : segs) {
            if (l > last) {
                ++ans;
                last = r;
            }
        }
        cout << "Case " << tc++ << ": " << ans << '\n';
    }
    return 0;
}

易错提醒

如果有 `y > d`，直接无解。
要按右端点排序，不是左端点。
浮点比较时通常用 `l > last` 即可，这题数据足够稳。

4034 选择客栈贪心 / 扫描黄进阶

题目链接

基本思路

从左到右扫描。`num[color]` 记录该颜色出现过多少次，`ok[color]` 记录“截至最近一次出现低价咖啡馆位置”为止，该颜色有多少客栈可以与当前位置配对。如果当前客栈咖啡馆价格 `<= p`，就把所有颜色的 `ok` 同步成当前 `num`。

标准代码

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

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

    int n, k, p;
    cin >> n >> k >> p;
    vector<long long> num(k, 0), ok(k, 0);
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        int c, cost;
        cin >> c >> cost;
        if (cost <= p) {
            for (int j = 0; j < k; ++j) ok[j] = num[j];
        }
        ans += ok[c];
        num[c]++;
    }
    cout << ans << '\n';
    return 0;
}

易错提醒

这题不是简单“同色配对数”，中间必须有一家价格不超过 `p` 的咖啡馆。
`n` 最多 200000，答案要用 `long long`。
`k` 很小，允许每次低价咖啡馆出现时遍历所有颜色。

4137 最小新整数贪心 / 单调栈黄易错

题目链接

基本思路

经典删数位。维护一个单调递增栈，当前数字比栈顶小且还可以删，就把栈顶弹掉。最后如果还没删够，就从末尾删。处理完后去掉前导零。

标准代码

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

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

    int T;
    cin >> T;
    while (T--) {
        string s;
        int k;
        cin >> s >> k;
        string st;
        for (char ch : s) {
            while (!st.empty() && k > 0 && st.back() > ch) {
                st.pop_back();
                --k;
            }
            st.push_back(ch);
        }
        while (k > 0 && !st.empty()) {
            st.pop_back();
            --k;
        }
        int pos = 0;
        while (pos < (int)st.size() && st[pos] == '0') ++pos;
        string ans = st.substr(pos);
        if (ans.empty()) ans = "0";
        cout << ans << '\n';
    }
    return 0;
}

易错提醒

删完后一定要处理前导零。
如果最后全删空了，输出 `0`。
别把它写成枚举删位，那样复杂度不对。

4144 畜栏保留问题贪心 + 堆黄主练

题目链接

基本思路

按开始时间排序，用小根堆维护每个畜栏当前最早的结束时间。若堆顶结束时间 `<` 当前开始时间，就复用该畜栏；否则新开一个畜栏。

标准代码

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

struct Cow {
    int l, r, id;
};

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

    int n;
    cin >> n;
    vector<Cow> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }
    sort(a.begin(), a.end(), [](const Cow& x, const Cow& y) {
        return x.l < y.l;
    });

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<int> ans(n);
    int stalls = 0;

    for (auto &c : a) {
        if (!pq.empty() && pq.top().first < c.l) {
            auto [endt, sid] = pq.top(); pq.pop();
            ans[c.id] = sid;
            pq.push({c.r, sid});
        } else {
            ++stalls;
            ans[c.id] = stalls;
            pq.push({c.r, stalls});
        }
    }

    cout << stalls << '\n';
    for (int x : ans) cout << x << '\n';
    return 0;
}

易错提醒

区间是闭区间，所以能复用的条件是 `前一头牛结束时间 < 当前开始时间`。
输出顺序要按原输入顺序，不是按排序后的顺序。
堆里除了结束时间还要存畜栏编号。

4151 电影节区间贪心绿先做

题目链接

基本思路

标准区间选择。按结束时间升序排序，能看就看，维护当前最后一部电影的结束时间。

标准代码

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

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

    int n;
    while (cin >> n, n) {
        vector<pair<int,int>> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
        sort(a.begin(), a.end(), [](auto& x, auto& y) {
            if (x.second != y.second) return x.second < y.second;
            return x.first < y.first;
        });
        int ans = 0, last = -1e9;
        for (auto& [l, r] : a) {
            if (l >= last) {
                ++ans;
                last = r;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

易错提醒

题目允许端点重合，所以条件是 `start >= last_end`。
多组数据以 `n = 0` 结束。
按结束时间排序，不是开始时间。

动态规划

1088 滑雪记忆化搜索 / DP黄主练

题目链接

基本思路

`dfs(x, y)` 表示从 `(x, y)` 出发能滑出的最长路径。向四个方向搜严格更低的点，用记忆化避免重复计算。

标准代码

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

int r, c;
int h[105][105], f[105][105];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dfs(int x, int y) {
    if (f[x][y] != -1) return f[x][y];
    f[x][y] = 1;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c && h[nx][ny] < h[x][y]) {
            f[x][y] = max(f[x][y], dfs(nx, ny) + 1);
        }
    }
    return f[x][y];
}

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

    cin >> r >> c;
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            cin >> h[i][j];

    memset(f, -1, sizeof f);
    int ans = 0;
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            ans = max(ans, dfs(i, j));
    cout << ans << '\n';
    return 0;
}

易错提醒

只能走向严格更低的格子。
`dfs` 返回的是“从这里开始”的答案，不是全局答案。
别忘记 `memset(f, -1, ...)`。

1159 Palindrome DP黄易错

题目链接

基本思路

最少插入字符数 = `n - 最长回文子序列长度`。最长回文子序列可以转化成原串和反串的 LCS，用滚动数组做，空间 `O(n)`。

标准代码

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

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

    int n;
    string s;
    cin >> n >> s;
    string t = s;
    reverse(t.begin(), t.end());

    vector<int> dp(n + 1, 0), pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        swap(dp, pre);
        fill(dp.begin(), dp.end(), 0);
        for (int j = 1; j <= n; ++j) {
            if (s[i - 1] == t[j - 1]) dp[j] = pre[j - 1] + 1;
            else dp[j] = max(pre[j], dp[j - 1]);
        }
    }
    cout << n - dp[n] << '\n';
    return 0;
}

易错提醒

`n` 到 5000，别开二维 `5000 x 5000 int`。
大小写是区分的，别做任何统一化处理。
如果你写区间 DP，也能过，但实现更容易写错。

1163 The Triangle DP绿先做

题目链接

基本思路

自底向上转移：`f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1])`。最后 `f[1][1]` 就是答案。

标准代码

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

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

    int n;
    cin >> n;
    vector<vector<int>> a(n + 2, vector<int>(n + 2, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            cin >> a[i][j];

    for (int i = n - 1; i >= 1; --i)
        for (int j = 1; j <= i; ++j)
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);

    cout << a[1][1] << '\n';
    return 0;
}

易错提醒

这题最稳的是自底向上，边界最少。
别把下标写成从 `0` 开始又没统一处理。

1170 Shopping Offers 状态压缩 DP偏黄压轴

题目链接

基本思路

商品种类最多只有 5 种，把购物篮状态压成 5 维小范围状态。普通单买也当成优惠方案，做记忆化搜索或状态 DP，求最小花费。

标准代码

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

struct Offer {
    int cnt[5]{};
    int price;
};

int basePow[6];
vector<Offer> offers;
int need[5], b;
unordered_map<int, int> memo;

int encode(const int a[]) {
    int s = 0;
    for (int i = 0; i < b; ++i) s += a[i] * basePow[i];
    return s;
}

int dfs(int state) {
    if (state == 0) return 0;
    if (memo.count(state)) return memo[state];

    int cur[5]{};
    int tmp = state;
    for (int i = 0; i < b; ++i) {
        cur[i] = tmp % 6;
        tmp /= 6;
    }

    int ans = INT_MAX / 2;
    for (auto &of : offers) {
        int nxt[5];
        bool ok = true;
        for (int i = 0; i < b; ++i) {
            if (cur[i] < of.cnt[i]) { ok = false; break; }
            nxt[i] = cur[i] - of.cnt[i];
        }
        if (ok) ans = min(ans, dfs(encode(nxt)) + of.price);
    }
    return memo[state] = ans;
}

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

    basePow[0] = 1;
    for (int i = 1; i <= 5; ++i) basePow[i] = basePow[i - 1] * 6;

    cin >> b;
    map<int, int> id;
    vector<int> code(b), price(b);
    for (int i = 0; i < b; ++i) {
        cin >> code[i] >> need[i] >> price[i];
        id[code[i]] = i;
    }

    int s;
    cin >> s;
    offers.clear();
    for (int i = 0; i < s; ++i) {
        Offer of;
        int n;
        cin >> n;
        for (int j = 0; j < n; ++j) {
            int c, k;
            cin >> c >> k;
            if (id.count(c)) of.cnt[id[c]] = k;
        }
        cin >> of.price;
        offers.push_back(of);
    }

    for (int i = 0; i < b; ++i) {
        Offer of;
        of.cnt[i] = 1;
        of.price = price[i];
        offers.push_back(of);
    }

    memo.clear();
    cout << dfs(encode(need)) << '\n';
    return 0;
}

易错提醒

只关心购物篮里出现的商品，其它代码可以忽略。
普通单买也要当成一种“方案”加入，否则状态转不回去。
每种商品数量最多 5，常用 `6` 进制压状态。

1185 炮兵阵地状态压缩 DP偏黄压轴

题目链接

基本思路

先枚举每一行的合法摆放状态：同一行不能相邻，也不能隔一个相邻。然后做三维 DP：`dp[row][state_cur][state_pre]`，检查和前两行是否冲突。

标准代码

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

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

    int n, m;
    cin >> n >> m;
    vector<int> g(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j)
            if (s[j] == 'H') g[i] |= (1 << j);
    }

    vector<int> state, cnt;
    for (int s = 0; s < (1 << m); ++s) {
        if ((s & (s << 1)) == 0 && (s & (s << 2)) == 0) {
            state.push_back(s);
            cnt.push_back(__builtin_popcount((unsigned)s));
        }
    }

    int S = state.size();
    vector dp(n + 1, vector(S, vector<int>(S, -1)));
    for (int i = 0; i < S; ++i) {
        if ((state[i] & g[1]) == 0) dp[1][i][0] = cnt[i];
    }

    for (int row = 2; row <= n; ++row) {
        for (int i = 0; i < S; ++i) {
            if (state[i] & g[row]) continue;
            for (int j = 0; j < S; ++j) {
                if (state[j] & g[row - 1]) continue;
                if (state[i] & state[j]) continue;
                for (int k = 0; k < S; ++k) {
                    if (dp[row - 1][j][k] == -1) continue;
                    if (state[i] & state[k]) continue;
                    dp[row][i][j] = max(dp[row][i][j], dp[row - 1][j][k] + cnt[i]);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < S; ++i)
        for (int j = 0; j < S; ++j)
            ans = max(ans, dp[n][i][j]);
    cout << ans << '\n';
    return 0;
}

易错提醒

同一行不仅不能相邻，间隔 1 也不行，所以要检查 `s & (s << 2)`。
当前行要同时和前一行、前两行检查冲突。
`H` 表示山地，当前状态不能压到山地上。

1661 帮助 Jimmy DP黄进阶

题目链接

基本思路

平台按高度从高到低排序。`dp[i][0/1]` 表示落到第 `i` 个平台左/右端点后，到地面的最短时间。转移时寻找该端点正下方的第一块平台。

标准代码

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

struct Node {
    int l, r, h;
} a[1005];

int dp[1005][2];
int n, X, Y, MAXH;

int findBelow(int x, int h) {
    for (int i = 1; i <= n; ++i) {
        if (a[i].h < h && a[i].l <= x && x <= a[i].r) return i;
    }
    return 0;
}

int solve(int i, int side) {
    int &res = dp[i][side];
    if (res != -1) return res;
    int x = (side == 0 ? a[i].l : a[i].r);
    int j = findBelow(x, a[i].h);
    if (!j) {
        if (a[i].h > MAXH) return res = 1e9;
        return res = a[i].h;
    }
    int down = a[i].h - a[j].h;
    if (down > MAXH) return res = 1e9;
    res = min(solve(j, 0) + abs(x - a[j].l), solve(j, 1) + abs(x - a[j].r)) + down;
    return res;
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> X >> Y >> MAXH;
        for (int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r >> a[i].h;
        sort(a + 1, a + n + 1, [](const Node& A, const Node& B) {
            return A.h > B.h;
        });
        memset(dp, -1, sizeof dp);

        int idx = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i].l <= X && X <= a[i].r && a[i].h < Y) {
                idx = i;
                break;
            }
        }
        if (!idx) cout << Y << '\n';
        else if (Y - a[idx].h > MAXH) cout << "1000000000\n";
        else {
            int ans = min(solve(idx, 0) + X - a[idx].l, solve(idx, 1) + a[idx].r - X) + (Y - a[idx].h);
            cout << ans << '\n';
        }
    }
    return 0;
}

易错提醒

平台按高度降序后，向下找第一块能接住的位置。
如果某次下落超过 `MAX`，这条路直接不可行。
起点是空中，不是某个平台本身。

2726 / 2727 / 2773 采药类 0/1 背包绿先做

2726 / 2727 / 2773

基本思路

这几题题面本质都是：时间是容量，草药价值是收益，每株只能采一次，因此是标准 0/1 背包。`f[j]` 表示总时间不超过 `j` 时的最大价值。

标准代码

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

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

    int T, M;
    cin >> T >> M;
    vector<int> f(T + 1, 0);
    for (int i = 0; i < M; ++i) {
        int t, v;
        cin >> t >> v;
        for (int j = T; j >= t; --j) {
            f[j] = max(f[j], f[j - t] + v);
        }
    }
    cout << f[T] << '\n';
    return 0;
}

易错提醒

内层必须倒序枚举，保证每株草药只用一次。
别把它误写成完全背包。
`f[j]` 是“容量不超过 j 的最优值”，不是恰好装满。

2755 神奇的口袋计数 DP绿先做

题目链接

基本思路

统计选若干物品体积和恰好为 40 的方案数。用 0/1 背包计数，`f[j]` 表示凑出体积 `j` 的方案数。

标准代码

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

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

    int n;
    cin >> n;
    vector<long long> f(41, 0);
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        for (int j = 40; j >= x; --j)
            f[j] += f[j - x];
    }
    cout << f[40] << '\n';
    return 0;
}

易错提醒

这是“方案数”，不是“最大价值”。
`f[0] = 1` 是计数 DP 的核心初始化。
仍然要倒序枚举，因为每件物品只能选一次。

2760 数字三角形 DP绿先做

题目链接

基本思路

和 `1163` 完全同型，自底向上 DP。

标准代码

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

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

    int n;
    cin >> n;
    vector<vector<int>> a(n + 2, vector<int>(n + 2, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            cin >> a[i][j];
    for (int i = n - 1; i >= 1; --i)
        for (int j = 1; j <= i; ++j)
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
    cout << a[1][1] << '\n';
    return 0;
}

易错提醒

这题就是经典模板，适合练“看见题型就秒写”。
别把路径限制写成能走三个方向。

3262 新数字三角形 DP绿模板变形

题目链接

基本思路

先把从每个位置出发到最底层的最大路径和都算出来，状态还是 `f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1])`。最后输出指定起点 `(R, C)` 的值。

标准代码

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

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

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<vector<int>> a(n + 2, vector<int>(n + 2, 0));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
                cin >> a[i][j];
        int R, C;
        cin >> R >> C;
        for (int i = n - 1; i >= 1; --i)
            for (int j = 1; j <= i; ++j)
                a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
        cout << a[R][C] << '\n';
    }
    return 0;
}

易错提醒

这是多组数据，`n = 0` 结束。
别误以为只能从顶点开始，本题起点是给定的。

4118 开餐馆 DP黄主练

题目链接

基本思路

典型一维 DP。`dp[i]` 表示考虑前 `i` 个地点的最大利润。转移：不选 `i`，或者选 `i` 并接上距离它超过 `k` 的最后一个位置。

标准代码

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

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

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> m(n + 1), p(n + 1), dp(n + 1, 0);
        for (int i = 1; i <= n; ++i) cin >> m[i];
        for (int i = 1; i <= n; ++i) cin >> p[i];
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            int j = i - 1;
            while (j >= 1 && m[i] - m[j] <= k) --j;
            dp[i] = max(dp[i], dp[j] + p[i]);
        }
        cout << dp[n] << '\n';
    }
    return 0;
}

易错提醒

题目要求距离必须“大于 `k`”，不是大于等于。
`n < 100`，直接 `O(n^2)` 就够，不必过度优化。
每组数据都要重新初始化 `dp`。

4121 股票买卖状态机 DP黄易错

题目链接

基本思路

最多做两次交易，用四个状态维护：第一次买入、第一次卖出、第二次买入、第二次卖出。每天更新一次。

标准代码

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        long long buy1 = LLONG_MIN / 4, sell1 = 0;
        long long buy2 = LLONG_MIN / 4, sell2 = 0;
        for (int i = 0; i < n; ++i) {
            long long x;
            cin >> x;
            buy1 = max(buy1, -x);
            sell1 = max(sell1, buy1 + x);
            buy2 = max(buy2, sell1 - x);
            sell2 = max(sell2, buy2 + x);
        }
        cout << sell2 << '\n';
    }
    return 0;
}

易错提醒

同一天允许“卖完再买”，所以状态转移顺序要统一。
价格可能为负，别把初值随便设成 `-1e9` 这种太小的数。
最多两次交易，不是无限次。

4122 切割回文区间 DP / 线性 DP黄易错

题目链接

基本思路

先预处理 `pal[i][j]` 表示子串 `s[i..j]` 是否回文。再设 `dp[i]` 表示前 `i` 个字符最少切几刀，枚举最后一段回文串的起点。

标准代码

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

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

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int n = s.size();
        vector<vector<bool>> pal(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = true;
            }
        }
        vector<int> dp(n + 1, 1e9);
        dp[0] = -1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (pal[j][i - 1]) dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        cout << dp[n] << '\n';
    }
    return 0;
}

易错提醒

`dp[0] = -1` 这个技巧能让整串本身是回文时答案自然变成 0。
回文预处理顺序要从短串推到长串，通常 `i` 倒着扫。
不要把“最少回文段数”和“最少切割次数”混起来。

4131 Charm Bracelet 0/1 背包绿先做

题目链接

基本思路

标准 0/1 背包。`f[j]` 表示容量不超过 `j` 时的最大 desirability。每个饰品最多使用一次，所以倒序枚举容量。

标准代码

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

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

    int N, M;
    cin >> N >> M;
    vector<int> f(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        int w, d;
        cin >> w >> d;
        for (int j = M; j >= w; --j)
            f[j] = max(f[j], f[j - w] + d);
    }
    cout << f[M] << '\n';
    return 0;
}

易错提醒

别写成完全背包，饰品每个只能用一次。
容量 `M` 比较大，但一维数组足够。

4149 课程大作业状压 DP偏黄压轴

题目链接

基本思路

`N <= 15`，用状压 DP。`dp[mask]` 表示完成 `mask` 这些课程的最小扣分，`time[mask]` 表示完成这些课程总共花的时间。转移时枚举最后做哪门课。若扣分相同，按字典序更小的方案更新。

标准代码

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

struct Course {
    string name;
    int d, c;
};

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<Course> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i].name >> a[i].d >> a[i].c;

        int N = 1 << n;
        vector<int> dp(N, INT_MAX / 2), tim(N, 0);
        vector<string> path(N, "");
        dp[0] = 0;

        for (int mask = 1; mask < N; ++mask) {
            for (int i = 0; i < n; ++i) {
                if (!(mask & (1 << i))) continue;
                int pre = mask ^ (1 << i);
                int nowTime = tim[pre] + a[i].c;
                int penalty = dp[pre] + max(0, nowTime - a[i].d);
                string cand = path[pre] + a[i].name + "\n";
                if (penalty < dp[mask] || (penalty == dp[mask] && cand < path[mask])) {
                    dp[mask] = penalty;
                    tim[mask] = nowTime;
                    path[mask] = cand;
                }
            }
        }

        cout << dp[N - 1] << '\n' << path[N - 1];
    }
    return 0;
}

易错提醒

罚分是 `max(0, 完成时间 - 截止时间)`，不是简单差值累加。
相同最优值时要输出字典序更小的方案。
这题不是贪心，必须用状压 DP。

DP / 贪心题解整理

推荐顺序 · 贪心

推荐顺序 · DP

贪心

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

动态规划

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒

基本思路

标准代码

易错提醒