求AC的c++题解！

Question

c++题目求解！！

果蔬超市
题目背景
兔兔种了很多胡萝卜，但是今年大丰收，他自己根本吃不完，决定去果蔬超市把胡萝卜换成好吃的大白
菜、美味的水果等
题目描述
水果超市从前往后有n个摊子，每个摊位只卖一种果蔬，并且所有摊子卖的果蔬互不相同(如一号摊位卖白
菜、二号摊位卖番茄、三号摊位卖苹果等）。
兔兔必须从第一个摊位出发，可以用手里的胡萝卜交换尽可能多的第一种果蔬，之后在第二个摊位用手里
刚交换来的第一个摊位果蔬去交换尽可能多的第二个摊位果蔬以此类推，每到一个摊位，兔兔都
可以用上一个摊位得到的果蔬来交换当前摊位的果蔬。
并且每个摊位交换的比例并不相同，具体是上一个摊位的ai个果蔬可以换当前摊位bi个果蔬。
兔兔发现每一次虽然他都用尽可能多的果蔬去交换，但仍有不足以交换的果蔬会剩下，加上到第n个摊位
交换来的果蔬，兔兔会把最终的所有果蔬带回家，请帮忙计算它最终带回去多少果蔬。
输入格式
输入第一行两个正整数，分别表示摊位总数n个，与最初兔兔的胡萝卜数量s，
接下来连续n行，每行两个正整数ai，bi，表示第i个摊位需要用上一个摊位每a；个果蔬来交换到bi个果蔬。
输出格式
输出一个整数，表示兔兔带回家的果蔬数量（一个、一只、一条、一块都按一计算）
样例#1
样例输入#1
5 10
35
2 1
34
63
11
样例输出#1
8
提示
1≤n≤1000,
1<s≤10000,
1 ≤ ai,bi ≤ 100,
数据保证所有的计算过程不超过2×109
本题可以修改为每个摊位不一定尽可能多的交换，然后求兔兔最多可获得多少种果蔬或求兔兔最多可带走
多少果蔬

---

希望尽快回复，xiexie

Answer 1

【以下回答由 GPT 生成】

### 解决方案

这个问题可以使用动态规划来解决。主要的思路是，对于每一个摊位 i，我们需要计算在手里有 j 个胡萝卜的情况下，能够交换到的最多果蔬数量 dp[i][j]。

首先，我们需要创建一个二维数组 dp，大小为 (n+1)x(s+1)，其中 n 是摊位总数，s 是最初兔兔的胡萝卜数量。dp[i][j] 表示在第 i 个摊位，手里有 j 个胡萝卜的情况下，能够交换到的最多果蔬数量。

然后，我们可以使用动态规划的思路来计算 dp 数组的值。具体的算法如下：

1. 初始化 dp 数组：将所有的值都设为 0。
2. 对于每一个摊位 i（从 1 到 n），对于每一个可能的胡萝卜数量 j（从 0 到 s），计算 dp[i][j] 的值：
   a. 初始化 dp[i][j] 为 dp[i-1][j]，表示当前摊位不交换任何胡萝卜。
   b. 对于每一个能够交换到的果蔬数量 k（从 1 到 bi），计算 dp[i][j] 的最大值：
      - 如果 j >= k * ai（说明手里的胡萝卜足够交换到 k 个果蔬），那么更新 dp[i][j] 为 dp[i-1][j-k*ai] + k*bi。
      - 如果 j < k * ai（说明手里的胡萝卜不足以交换到 k 个果蔬），停止循环。

最终，返回 dp[n][s]，即为兔兔带回家的果蔬数量。

下面是具体的 C++ 代码实现：

```cpp
#include <iostream>
#include <vector>

using namespace std;

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

    vector<vector<int>> dp(n + 1, vector<int>(s + 1, 0));

    for (int i = 1; i <= n; i++) {
        int ai, bi;
        cin >> ai >> bi;

        for (int j = 0; j <= s; j++) {
            dp[i][j] = dp[i-1][j];

            for (int k = 1; k <= bi; k++) {
                if (j >= k * ai) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k*ai] + k*bi);
                } else {
                    break;
                }
            }
        }
    }

    cout << dp[n][s] << endl;

    return 0;
}

这个解法的时间复杂度为 O(n * s * bmax)，其中 bmax 是所有摊位的最大 bi 值。```

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7743683
• 除此之外, 这篇博客: Educational Codeforces Round 102 (Rated for Div. 2)中的 思路：首先考虑在没有删除的情况下，一系列操作过程中，能变成多少不同的值。x初始为0，随着+±-的变化，会来回反复横跳，那么两个关键点就是最大值和最小值，这说明从最大值到最小值之间的数字，都是在操作过程中出现。所以只需要考虑一个区间内的操作产生的最大最小值。但是题目要删掉，中间一段，剩下两段，也就是要把两段合并起来。画个图其实更好理解。红色的是所有的操作，绿色的是要删除的操作，第二个曲线就是合并之后的x值变化曲线。由图可知。后面那部分合并过来之后，起点就是前面那部分的终点！这就是关键点。然后前面那部分的区间的最大最小值和当前值都很好维护。难的是后面那部分怎么维护。后面那部分，从后往前维护，每到一个点，都认为这个点是零点，然后计算最大值最小值。因为是反着来，可以发现操作曲线是一个与 原操作 关于x轴对称的曲线，所以最大值就是最小值，最小值就是最大值。然后最小值就是 当前点到最小值的距离，最大值就是 当前点到最大值的距离。之所以算距离，是因为，永远认为当前点是0点。所以 距离 才是真正的最大最小值。 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^