https://www.luogu.com.cn/problem/P2918

[USACO08NOV] Buying Hay S

题目描述

Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.

He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P_i (1 <= P_i <= 5,000) pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.

约翰的干草库存已经告罄，他打算为奶牛们采购 $H(1 \leq H \leq 50000)$ 磅干草。

他知道 $N(1 \leq N\leq 100)$ 个干草公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 公司卖的干草包重量为 $P_i (1 \leq P_i \leq 5,000)$ 磅，需要的开销为 $C_i (1 \leq C_i \leq 5,000)$ 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。

帮助约翰找到最小的开销来满足需要，即采购到至少 $H$ 磅干草。

输入格式

* Line 1: Two space-separated integers: N and H

* Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i

输出格式

* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.

样例 #1

样例输入 #1

2 15 
3 2 
5 3

样例输出 #1

9

提示

FJ can buy three packages from the second supplier for a total cost of 9.

const int N = 5e5 + 10;
int dp[110][60000];
int p[110], c[110];
void solve()
{
    int n, h;
    cin >> n >> h;
    int m = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i] >> c[i];
        m = max(p[i], m);
    }
    m += h;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 1e9;
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= p[i] && dp[i][j - p[i]] != 1e9)
            {
                dp[i][j] = min(dp[i][j], dp[i][j - p[i]] + c[i]);
            }
        }
    }
    int ans=1e9;
    for (int i = h; i <= m; i++) ans = min(ans, dp[n][i]);
    cout << ans << '\n';
}