题意分析

你受雇于一家生产黄铜砖的工厂，需要为客户提供服务。工厂生产多种不同类型的黄铜砖，每种砖有不同的铜含量和价格。客户的需求是购买一定数量（$M$）的不同类型的砖，这些砖混合后每千克的铜含量必须在一个指定的范围（$CMin$ 到 $CMax$）内，且客户希望购买这些砖的总价格最小。

输入包括两部分：

1. 第一部分是一个整数 $N$，表示砖的类型数量，随后有 $N$ 行，每行包含每种砖的铜含量和价格。
2. 第二部分是一个整数 $C$，表示客户数量，随后有 $C$ 行，每行包含每个客户的 $M$、$CMin$ 和 $CMax$。

输出要求为每个客户输出一行，包含满足其需求的最小购买价格。如果无法满足需求，则输出 “impossible”。

解题思路

本题可使用动态规划来解决。核心思路是通过一个二维数组 $f[j][v]$ 来记录选择 $j$ 块砖且总铜含量为 $v$ 时的最小总价格。具体步骤如下：

1. 初始化：将 $f$ 数组除 $f[0][0]$ 初始化为 0 外，其余元素初始化为无穷大 $INF$，表示初始状态下除了不选砖（$j = 0$ 且 $v = 0$）价格为 0 外，其他情况暂未找到可行方案。
2. 状态转移：对于每一种砖，从最大的 $M$ 值开始递减，对于每个 $j$，再从最大的总铜含量 $max_weight$ 开始递减到当前砖的铜含量，通过状态转移方程 $f[j][v] = min(f[j][v], f[j - 1][v - copper[i]] + price[i])$ 更新 $f$ 数组，其中 $copper[i]$ 是当前砖的铜含量，$price[i]$ 是当前砖的价格。
3. 结果计算：对于每个客户，遍历总铜含量在 $CMin * M$ 到 $CMax * M$ 范围内的所有情况，找出最小价格。若最小价格仍为无穷大，则表示无法满足该客户需求。

示例代码

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MP make_pair
#define SQ(x) ((x)*(x))

using namespace std;
typedef long long int64;

const double PI = acos(-1.0);
const int MAXN = 210;
const int INF = 0x3f3f3f3f;
int n, m, copper[MAXN], price[MAXN];
int M[MAXN], CMin[MAXN], CMax[MAXN];
int f[22][20010];

int main(){

    while(~scanf("%d", &n)){
        
        for(int i = 0; i < n; ++i)
            // 读取每种砖的铜含量和价格
            scanf("%d%d", &copper[i], &price[i]);

        scanf("%d", &m);
        int max_M = 0, max_weight = 0;
        for(int i = 0; i < m; ++i){
            // 读取每个客户的 M、CMin 和 CMax
            scanf("%d%d%d", &M[i], &CMin[i], &CMax[i]);
            if(M[i] > max_M) max_M = M[i];
            if(CMax[i] * M[i] > max_weight) max_weight = CMax[i] * M[i];
        }

        // 初始化动态规划数组
        memset(f, INF, sizeof(f));
        f[0][0] = 0;
        for(int i = 0; i < n; ++i){
            for(int j = max_M; j >= 1; --j){
                for(int v = max_weight; v >= copper[i]; --v){
                    // 状态转移方程
                    f[j][v] = min(f[j][v], f[j - 1][v - copper[i]] + price[i]);
                }
            }
        }

        for(int i = 0; i < m; ++i){
            int minx = INF;
            for(int j = CMin[i] * M[i]; j <= CMax[i] * M[i]; ++j)
                if(f[M[i]][j] < minx) 
                    // 找出满足客户需求的最小价格
                    minx = f[M[i]][j];
            if(minx == INF) puts("impossible");
            else printf("%d\n", minx);
        }
    }
    return 0;
}    

代码解释

1. 全局变量：
   • $n$：砖的类型数量。
   • $m$：客户数量。
   • $copper[MAXN]$：存储每种砖的铜含量。
   • $price[MAXN]$：存储每种砖的价格。
   • $M[MAXN]$：存储每个客户需要的砖的数量。
   • $CMin[MAXN]$：存储每个客户要求的最小铜含量。
   • $CMax[MAXN]$：存储每个客户要求的最大铜含量。
   • $f[22][20010]$：动态规划数组，$f[j][v]$ 表示选择 $j$ 块砖且总铜含量为 $v$ 时的最小总价格。
2. 输入处理：
   • 首先读取砖的类型数量 $n$，并循环读取每种砖的铜含量和价格。
   • 接着读取客户数量 $m$，并循环读取每个客户的 $M$、$CMin$ 和 $CMax$，同时记录最大的 $M$ 值和最大的总铜含量 $max_weight$。
3. 动态规划数组初始化：
   • 使用 $memset(f, INF, sizeof(f))$ 将 $f$ 数组所有元素初始化为无穷大。
   • 将 $f[0][0]$ 初始化为 0，表示不选砖时总铜含量为 0，价格为 0。
4. 动态规划状态转移：
   • 外层循环遍历每种砖。
   • 中层循环从最大的 $M$ 值递减到 1。
   • 内层循环从最大的总铜含量 $max_weight$ 递减到当前砖的铜含量。
   • 通过状态转移方程 $f[j][v] = min(f[j][v], f[j - 1][v - copper[i]] + price[i])$ 更新 $f$ 数组。
5. 结果计算：
   • 对于每个客户，遍历总铜含量在 $CMin * M$ 到 $CMax * M$ 范围内的所有情况，找出最小价格 $minx$。
   • 若 $minx$ 仍为无穷大，则输出 “impossible”；否则输出 $minx$。

注意事项

1. 输入范围：要注意输入的砖的类型数量 $N$、客户数量 $C$、砖的铜含量、价格以及客户的 $M$、$CMin$ 和 $CMax$ 的取值范围，确保代码能正确处理这些输入。
2. 无穷大表示：使用 $INF = 0x3f3f3f3f$ 表示无穷大，在状态转移过程中要确保不会出现溢出问题。
3. 输出格式：对于无法满足客户需求的情况，要准确输出 “impossible”，且每个客户的结果输出在单独一行。