更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解
原题链接： 202406-4 货物调度
时间限制： 2.0 秒
空间限制： 512 MiB
题目描述
西西艾弗岛上共有 n n n 间物流仓库，小 P 目前有 m m m 件货物存放其中。为了获得至少为 v v v 的现金，小 P P P 需要选取一些货物卖出。
已知货物信息如下，第 i i i 件（ 0 ≤ i < m 0 \le i < m 0≤i<m）货物：
存放在第 t i t_i ti 间仓库中（ 0 ≤ t i < n 0 \le t_i < n 0≤ti<n）；
价值为 a i a_i ai，即选择卖出该货物可获得 a i a_i ai 的现金。
但在调货出库时也需要支付一些费用，对于第 j j j 间（ 0 ≤ j < n 0 \le j < n 0≤j<n）仓库：
只要调用了该仓库的货物（至少一件），就需要支付 b j b_j bj 的基本费用；
如果调用了该仓库中共 k k k 件货物，则还需要支付 k × c j k \times c_j k×cj 的计件费用。
小 P 的最终目标是获得至少为 v v v 的现金，即要求卖出的货物总价值减去总费用的结果大于或等于 v v v。 在满足该目标的前提下，试为小 P P P 规划一种花费最小的卖货方案。
输入格式
从标准输入读入数据。
输入的第一行包含三个正整数 n n n、 m m m 和 v v v。
接下来 n n n 行输入仓库信息，其中第 j j j 行（ 0 ≤ j < n 0 \le j < n 0≤j<n）包含两个整数 b j b_j bj 和 c j c_j cj。
接下来 m m m 行输入货物信息，其中第 i i i 行（ 0 ≤ i < m 0 \le i < m 0≤i<m）包含两个整数 a i a_i ai 和 t i t_i ti。
输出格式
输出到标准输出。
仅输出一个整数，表示完成目标前提下的最小花费。
样例1输入
2 3 152 13 210 020 115 0样例1输出
4样例1解释
最优方案：选取货物 0 0 0 和 2 2 2，二者均在 0 0 0 号仓库，总花费为 2 + 2 × 1 = 4 2 + 2 \times 1 = 4 2+2×1=4。
选取货物 1 1 1 也刚好能满足要求（ 20 − 3 − 1 × 2 ≥ 15 20 - 3 - 1 \times 2 \ge 15 20−3−1×2≥15），但花费更多。
单独选取货物 0 0 0 或 2 2 2 均不能满足要求。
样例2输入
5 3 152 11 13 24 21 510 110 110 1样例2输出
3样例2解释
小 P 所有货物均存放在仓库 1 1 1 中，任取两件货物卖出即可满足要求（ 10 + 10 − 1 − 2 × 1 ≥ 15 10 + 10 - 1 - 2 \times 1 \ge 15 10+10−1−2×1≥15）。
子任务
30 % 30\% 30% 的数据满足：
m ≤ 15 m \le 15 m≤15另有 40 % 40\% 40% 的数据满足：
a i ≤ 20 a_i \le 20 ai≤20全部的数据满足：
0 < n , m ≤ 1000 0 < n, m \le 1000 0<n,m≤1000
0 < b j , c j ≤ 20 0 < b_j, c_j \le 20 0<bj,cj≤20
0 < a i ≤ 1000 0 < a_i \le 1000 0<ai≤1000
0 < v ≤ 1 0 6 0 < v \le 10^{6} 0<v≤106 且保证至少存在一种可满足要求的卖货方案。
题解
待补
时间复杂度： O ( m × 20 ( n + m ) ) \mathcal{O}(m\times20(n+m)) O(m×20(n+m))。
参考代码（129ms，100056KB）
/* Created by Pujx on 2024/6/20.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include <bits/stdc++.h>using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;//using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout << (x ? "yes" : "no") << endl#define Yn(x) cout << (x ? "Yes" : "No") << endl#define YN(x) cout << (x ? "YES" : "NO") << endl#define mem(x, i) memset(x, i, sizeof(x))#define cinarr(a, n) for (int _ = 1; _ <= n; _++) cin >> a[_]#define cinstl(a) for (auto& _ : a) cin >> _#define coutarr(a, n) for (int _ = 1; _ <= n; _++) cout << a[_] << " \n"[_ == n]#define coutstl(a) for (const auto& _ : a) cout << _ << ' '; cout << endl#define all(x) (x).begin(), (x).end()#define md(x) (((x) % mod + mod) % mod)#define ls (s << 1)#define rs (s << 1 | 1)#define ft first#define se second#define pii pair<int, int>#ifdef DEBUG #include "debug.h"#else #define dbg(...) void(0)#endifconst int N = 1000 + 5;const int M = N * 40;const int mod = 998244353;//const int mod = 1e9 + 7;//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }int b[N], c[N];int n, m, t, k, q, v;vector<int> a[N];int dp[N][M]; //前i个仓库，花费为j时的最大净收益void work() { cin >> n >> m >> v; int C = 0; for (int i = 1; i <= n; i++) cin >> b[i] >> c[i], C += b[i]; for (int i = 1; i <= m; i++) { cin >> k >> t, ++t, C += c[t]; if (c[t] < k) a[t].emplace_back(k - c[t]); } for (int i = 1; i <= n; i++) { sort(all(a[i]), greater()); for (int j = 1; j < a[i].size(); j++) a[i][j] += a[i][j - 1]; } int ans = inf; for (int i = 1; i <= n; i++) { for (int j = 0; j <= C; j++) { dp[i][j] = dp[i - 1][j]; for (int k = 0; k < a[i].size(); k++) { if (j - b[i] - c[i] * (k + 1) < 0) break; dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i] - c[i] * (k + 1)] + a[i][k] - b[i]); } if (dp[i][j] >= v) ans = min(ans, j); } } cout << ans << endl;}signed main() {#ifdef LOCAL freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin); freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Case = 1; //cin >> Case; while (Case--) work(); return 0;}/* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\*/关于代码的亿点点说明：
代码的主体部分位于void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ... 是用来开启 O2、O3 等优化加快代码速度。中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。"debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。