T2-6 Buying Hay S

题意理解

有 $N$ 家公司卖干草，第 $i$ 家的干草包重 $P_i$ 磅、价格 $C_i$ 美元，每家货源无限。求购买至少 $H$ 磅干草的最小花费。

---

思路分析

这是完全背包的变种，关键在于"至少 $H$ 磅"而非"恰好 $H$ 磅"。

设 $dp[j]$ 表示：购买至少 $j$ 磅干草的最小花费。

状态转移：

对于每家公司 $(P_i, C_i)$，考虑买一包：

$$dp[j] = min(dp[j], dp[max(0, j - P_i)] + C_i)$$

当 $j - P_i < 0$ 时，从 $dp[0]$ 转移，表示买的比需要的多（这正是"至少"的含义）。

边界条件：

• $dp[0] = 0$：不需要干草，花费为 0
• $dp[j] = \infty$（$j > 0$）：初始无法达到

答案： $dp[H]$

---

参考代码

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

const int MAXH = 50005;  // 最大干草重量
const int INF = 0x3f3f3f3f;  // 无穷大

int n, H;          // 公司数量和需要的干草重量
int P[105], C[105];  // 每家公司的干草包重量和价格
int dp[MAXH];      // dp[j]表示购买至少j磅干草的最小花费

int main() {
    cin >> n >> H;  // 读入公司数量和需要的干草重量
    
    for (int i = 1; i <= n; i++) {  // 读入每家公司的信息
        cin >> P[i] >> C[i];
    }
    
    memset(dp, 0x3f, sizeof(dp));  // 初始化为无穷大
    dp[0] = 0;  // 边界：不需要干草，花费为0
    
    for (int i = 1; i <= n; i++) {  // 枚举每家公司
        for (int j = 1; j <= H; j++) {  // 完全背包，正序枚举重量
            int from = max(0, j - P[i]);  // 转移来源，允许超买
            dp[j] = min(dp[j], dp[from] + C[i]);  // 状态转移
        }
    }
    
    cout << dp[H] << endl;  // 输出答案
    return 0;
}