第 3 题 混合实验

题意分析

有 $N$ 个物体，第 $i$ 个物体含有 $a_i$ 质量的 A 元素和 $b_i$ 质量的 B 元素，选取代价为 $c_i$。

需要从 $N$ 个物体中选出至少一个，混合后满足：

• A 元素总质量 $S_A$ 与 B 元素总质量 $S_B$ 的比例恰好等于 $M_a : M_b$
• 在所有满足比例的方案中，总代价 $\sum c_i$ 最小

如果不存在可行方案，输出 $-1$。

关键约束：

• $1 \le N \le 40$
• $1 \le a_i, b_i \le 10$，$1 \le c_i \le 100$
• $1 \le M_a, M_b \le 10$，$gcd(M_a, M_b) = 1$

由于 $a_i, b_i \le 10$，$N \le 40$，所以 $S_A, S_B$ 的最大可能值都不超过 $400$。值域非常小，适合做二维 0/1 背包 DP。

---

思路分析

状态设计

设 $dp[i][j]$ 表示：使得 A 元素总和恰好为 $i$、B 元素总和恰好为 $j$ 时的最小代价。

• 初始状态：$dp[0][0] = 0$（什么都不选，代价为 0）
• 其他状态初始化为 $+infty$（不可达）

状态转移（0/1 背包，复制新表法）

对每个物品 $k$，做选/不选的决策：

• 不选：$ndp[i][j]$ 继承自 $dp[i][j]$（已通过 auto ndp = dp; 复制）
• 选：若 $dp[i][j]$ 可达，则 $ndp[i+a_k][j+b_k] = \min(ndp[i+a_k][j+b_k],\ dp[i][j] + c_k)$

每轮处理完一个物品后，把 ndp 赋回 dp，进入下一轮。这种先复制再更新的写法天然避免了同一物品被重复选取。

答案提取

由于 $gcd(M_a, M_b) = 1$，比例 $S_A : S_B = M_a : M_b$ 当且仅当存在正整数 $k$ 使 $S_A = k \cdot M_a$、$S_B = k \cdot M_b$。

枚举正整数 $k$，检查 $dp[k \cdot M_a][k \cdot M_b]$，取最小值。如果都不可达，输出 $-1$。

复杂度

• 状态数：$O(S_A \cdot S_B) = O(400 \times 400) = 1.6 \times 10^5$
• 总时间：$O(N \cdot S_A \cdot S_B) = 40 \times 400 \times 400 = 6.4 \times 10^6$
• 完全可以在 1 秒内跑完

---

代码实现（逐行解释）

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

int main() {
    int N, Ma, Mb;
    cin >> N >> Ma >> Mb;
    
    // 读入每个物品的 (a, b, c)
    vector<int> a(N), b(N), c(N);
    for(int i = 0; i < N; ++i) 
        cin >> a[i] >> b[i] >> c[i];
    
    // A、B 总和上限：N=40, a_i/b_i ≤ 10，所以最大 = 400
    const int max_sum = 400;
    
    // dp[i][j] 表示 A 总和=i、B 总和=j 时的最小代价
    // 初始化全为 INT_MAX 表示"不可达"
    vector<vector<int>> dp(max_sum + 1, vector<int>(max_sum + 1, INT_MAX));
    
    // 初始状态：什么都不选，A=0、B=0，代价为 0
    dp[0][0] = 0;
    
    // 逐个物品做 0/1 背包
    for(int k = 0; k < N; ++k) {
        // 关键：把整个 dp 复制一份到 ndp
        // 接下来"从 dp 读、向 ndp 写"，保证每个物品最多被选一次
        auto ndp = dp;
        
        // 枚举所有当前可达的 (i, j) 状态
        for(int i = 0; i <= max_sum; ++i) {
            for(int j = 0; j <= max_sum; ++j) {
                // 只有当前状态可达，才能基于它转移
                if(dp[i][j] != INT_MAX) {
                    // 选第 k 个物品后到达的新状态
                    int ni = i + a[k];
                    int nj = j + b[k];
                    
                    // 不能超出数组上限
                    if(ni <= max_sum && nj <= max_sum) {
                        // 更新新状态的最小代价
                        ndp[ni][nj] = min(ndp[ni][nj], dp[i][j] + c[k]);
                    }
                }
            }
        }
        
        // 用更新后的 ndp 替换旧 dp，进入下一轮
        dp = ndp;
    }
    
    // 在所有满足比例的状态中找最小代价
    // 因为 gcd(Ma, Mb) = 1，所以满足 sa:sb = Ma:Mb 的状态 ⇔ sa = k*Ma, sb = k*Mb
    int ans = INT_MAX;
    for(int k = 1; k * Ma <= max_sum && k * Mb <= max_sum; ++k) {
        if(dp[k * Ma][k * Mb] < ans) {
            ans = dp[k * Ma][k * Mb];
        }
    }
    
    // 如果没有任何可达状态，输出 -1，否则输出最小代价
    cout << (ans != INT_MAX ? ans : -1);
    return 0;
}