c++描述 P老师需要去商店买 n 支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有三种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起见,P老师决定只买同一种包装的铅笔。 商店不允许将铅笔的包装拆开,因此P老师可能需要购买超过 n 支铅笔才够给小朋友们发礼物。 现在P老师想知道,在商店每种包装的数量都足够的情况下,要买够至少 n 支铅笔最少需要花费多少钱。 输入描述 第一行包含一个正整数 n ,表示需要的铅笔数量。 接下来三行,每行用 2 个正整数描述一种包装的铅笔,其中: 第 1个整数表示这种包装内铅笔的数量 第 2个整数表示这种包装的价格。 保证所有的 2个数都是不超过 10000的正整数。 输出描述 1个整数,表示P老师最少需要花费的钱。
时间: 2024-02-12 20:04:33 浏览: 148
c++钱的问题
好的,下面是 C++ 代码实现:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;
int n;
int f[MAXN];
struct Pencil {
int num, price;
} p[3];
int main() {
cin >> n;
memset(f, INF, sizeof(f));
f[0] = 0;
for (int i = 0; i < 3; ++i) {
cin >> p[i].num >> p[i].price;
for (int j = p[i].num; j <= n; ++j) {
f[j] = min(f[j], f[j - p[i].num] + p[i].price);
}
}
cout << f[n] << endl;
return 0;
}
```
读入铅笔包装的数量和价格,从小到大枚举铅笔数量,使用状态转移方程更新 $f_i$ 的值。最后输出 $f_n$ 即可。
注意,由于初始化 $f$ 为 $+\infty$,因此不能直接加上 $p[i].price$ 来更新 $f_{j}$,否则会出现整型溢出的问题。
阅读全文