Day 27 · 完全背包 + DP 综合

题意：山洞里有 m 种草药，采第 i 种要花 a_i 的时间，能得到 b_i 的价值。 总共有 t 的时间。每种草药可以无限制地采。问最多能采到多少总价值。

它就是昨天 P1048 采药的改编版，唯一的改动是「每种可以无限采」。

思路

完全背包模板题。一维滚动数组，外层枚举草药种类，内层正序枚举时间。

注意输入顺序：第一行是 t 在前、m 在后（先时间，后草药种类数），别读反。

70 3
71 100
69 1
1 2

140

后两种草药一个要 69 时间只值 1，一个要 1 时间值 2。最优解是采第 3 种 70 次： 70 时间、70 × 2 = 140 价值。（第 1 种要 71 时间，超了，一次都采不了。）

完整代码

#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> w(m + 1), v(m + 1);
    for(int i = 1; i <= m; i++)
        cin >> w[i] >> v[i];

    // dp[j] = 时间限制为 j 时能采到的最大总价值（用 long long！）
    vector<long long> dp(t + 1, 0);

    for(int i = 1; i <= m; i++){
        // ★ 完全背包：容量正序枚举，j 从小到大
        for(int j = w[i]; j <= t; j++){
            if(dp[j - w[i]] + v[i] > dp[j])
                dp[j] = dp[j - w[i]] + v[i];
        }
    }

    cout << dp[t] << "\n";
    return 0;
}

易错点

• 内层写成倒序 → 退化成 0/1 背包，每种草药只能采一次 → 答案偏小。
• dp 用 int → 答案可达 10¹¹，直接溢出成负数或错误值。
• 第一行读反：题目是 t m（时间在前），写成 cin >> m >> t 就全错了。
• 数组开成 dp[t] 而不是 dp[t+1] → 下标 t 越界。
• 这题用 cin/cout 时建议加 ios::sync_with_stdio(false)，数据量大时更稳（我的代码加了）。

题意：有 n 个好友和 x 个「属性药」。对第 i 个人：打输了得 lose_i 经验； 想打赢至少要花 use_i 个药，赢了得 win_i 经验。 药花得不够 use_i 就必输，而且那些药也白白浪费。

求最多能拿到的经验 s，然后输出 5s。

思路

把「每个好友」看成一件物品，但它的决策有两个：

因为每个人只打一次，本质是 0/1 背包，所以容量倒序枚举。转移时对两个决策取 max。

另外注意 use_i = 0 的情况：不花药也能赢，而 win_i ≥ lose_i， 所以公式会自动选「打赢」，不需要特判。

6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2

1060

6 个人全打输保底 21+21+21+14+14+14 = 105 点。
用 8 个药去赢第 1、2、3 个人（花 1+5+2 = 8 个药），比打输多赚 (52−21)+(70−21)+(48−21) = 31+49+27 = 107 点。
总共 105 + 107 = 212，乘 5 就是 1060。

完整代码

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

int main(){
    int n, x;
    cin >> n >> x;

    vector<int> lose(n + 1), win(n + 1), use(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> lose[i] >> win[i] >> use[i];

    // dp[j] = 药最多用 j 个时，累计获得的最大经验
    vector<long long> dp(x + 1, 0);      // ★ long long

    for(int i = 1; i <= n; i++){
        // 0/1 背包：容量倒序枚举，保证每个人只被考虑一次
        for(int j = x; j >= 0; j--){
            long long a = dp[j] + lose[i];          // 这个人打输了
            long long b = -1;
            if(j >= use[i])                          // 药够，可以打赢
                b = dp[j - use[i]] + win[i];
            dp[j] = (a > b ? a : b);                 // ★ 两个决策取最优
        }
    }

    cout << dp[x] * 5 << "\n";       // ★ 输出 5 倍，必须 long long
    return 0;
}

易错点

• 只写了「打赢」的分支，药不够时忘了加 lose_i → 答案偏小。
• 最后乘 5 时用了 int → 5×10⁹ 溢出。dp 是 long long 也没用，要保证乘出来还是 long long。
• 容量写成正序 → 一个人被反复打了，答案偏大。
• 误以为「打输就不打这个人了」。题目里 6 个人是要全打的，打输也有 lose_i 经验。
• use_i 可以为 0，dp[j - use[i]] 就是 dp[j] 本身，这里的顺序要想清楚（我的代码用 a、b 两个临时变量，所以没问题）。

题意：把集合 {1, 2, 3, …, n} 划分成两个子集合，要求两个子集合里所有数字的和相等。 问一共有多少种划分方案。交换两个集合的位置算同一种方案。

思路

第一步：把问题翻译一下。

两个集合和相等，那么每个集合的和都必须是总和的一半。设 sum = n(n+1)/2。

第二步：转化成背包。 从 1 ~ n 里挑出若干个数字，让它们的和恰好等于 half —— 这问的是方案数。

dp[j] = 从 {1..n} 中选出若干个数、和恰好为 j 的方案数
转移：  dp[j] += dp[j - i]        // 数字 i 选或不选
初值：  dp[0] = 1                 // 「一个都不选」只有 1 种

每个数字只能用一次，所以内层倒序。

第三步：为什么要除以 2。

dp[half] 数的是「和为 half 的子集有多少个」。假设某个子集是 S，那它的补集就是另一半， S 和补集是同一个划分方案的两种写法。所以每个划分方案在 dp[half] 里被数了两次， 答案要除以 2。

7

4

n = 7 时 sum = 28，half = 14。和为 14 的子集有 8 个（就是题目列的 4 种划分 × 2 种写法）， dp[14] = 8，除以 2 得 4。

完整代码

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

int main(){
    int n;
    cin >> n;

    int sum = n * (n + 1) / 2;
    if(sum % 2 != 0){                 // ★ 总和是奇数，不可能平分
        cout << 0 << "\n";
        return 0;
    }
    int half = sum / 2;

    // dp[j] = 从 {1..n} 中选出若干数、和恰好为 j 的方案数
    vector<long long> dp(half + 1, 0);
    dp[0] = 1;                        // ★ 一个都不选，和为 0，算 1 种

    for(int i = 1; i <= n; i++)
        for(int j = half; j >= i; j--)   // 每个数只能用一次 -> 倒序
            dp[j] += dp[j - i];

    cout << dp[half] / 2 << "\n";     // ★ 两个集合互换算同一种，除以 2
    return 0;
}

易错点

• 忘记除以 2 → 输出恰好是正确答案的两倍。
• 忘记判断 sum 是奇数 → 会数出一个错误的非零答案。
• dp[0] 忘了设成 1 → 所有 dp 值都是 0，答案恒为 0。
• 内层写成正序 → 同一个数字被反复用，方案数暴涨。
• sum 用 int 算没问题（最大 780），但 dp 里的方案数要 long long（n = 39 时是 15 亿）。
• 内层循环下界写成 j >= 0 或 j >= 1：因为 j - i 必须 ≥ 0，所以条件是 j >= i，写成别的会数组越界。

题意：给一个 n × m 的、只含 0 和 1 的矩阵，找出一个不包含 0 的最大正方形， 输出它的边长。题目保证矩阵里至少有一个 1。

思路

让 dp[i][j] = 以 (i, j) 为右下角的最大全 1 正方形的边长。

• a[i][j] == 0 → dp[i][j] = 0（自己是 0，当不了全 1 正方形的角）
• a[i][j] == 1 → dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

最后扫一遍所有 dp 值取最大。复杂度 O(n·m) = 10⁴，飞快。

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

2

最大的全 1 正方形是左上角那块 2×2（(1,2)、(1,3)、(2,2)、(2,3)），边长 2。 没有更大的了，所以输出 2。

完整代码

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

int a[105][105];
int dp[105][105];        // 全局数组，自动全部初始化为 0

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == 1){
                // 左、上、左上 三个状态取最小，再加 1
                int mn = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                dp[i][j] = mn + 1;
                if(dp[i][j] > ans) ans = dp[i][j];
            }
        }
    }

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

易错点

• min 里只写两个状态（漏掉 dp[i-1][j-1]）→ 某些形状下边长算大，WA。三个都要写。
• 输出面积而不是边长：题目要的是边长，别写成 ans * ans。
• 把 dp 定义成局部数组 int dp[105][105];（在 main 里）→ 不会自动清零，边界值成了随机数。放全局就自动是 0。
• 数组开成 a[100][100]：下标要用到 n = 100，会越界。开 105 留余量。
• a[i][j] == 0 时不用手动赋值，全局数组本来就是 0；但如果你为了省事把 dp 清成别的数，这里就得补一句 dp[i][j] = 0;。