CCF-CSP认证考试 202406-4 货物调度 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202406-4 货物调度

时间限制： 2.0 秒
空间限制： 512 MiB

题目描述

西西艾弗岛上共有 $n$ 间物流仓库，小 P 目前有 $m$ 件货物存放其中。为了获得至少为 $v$ 的现金，小 $P$ 需要选取一些货物卖出。

已知货物信息如下，第 $i$ 件（$0\le i<m$）货物：

• 存放在第 $t_i$​ 间仓库中（$0\le t_i<n$）；

• 价值为 $a_i$，即选择卖出该货物可获得 $a_i$ 的现金。

但在调货出库时也需要支付一些费用，对于第 $j$ 间（$0\le j<n$）仓库：

• 只要调用了该仓库的货物（至少一件），就需要支付 $b_j$​ 的基本费用；

• 如果调用了该仓库中共 $k$ 件货物，则还需要支付 $k\times c_j$ 的计件费用。

小 P 的最终目标是获得至少为 $v$ 的现金，即要求卖出的货物总价值减去总费用的结果大于或等于 $v$。 在满足该目标的前提下，试为小 $P$ 规划一种花费最小的卖货方案。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n$、$m$ 和 $v$。

接下来 $n$ 行输入仓库信息，其中第 $j$ 行（$0\le j<n$）包含两个整数 $b_j$​ 和 $c_j$。

接下来 $m$ 行输入货物信息，其中第 $i$ 行（$0\le i<m$）包含两个整数 $a_i$​ 和 $t_i$。

输出格式

输出到标准输出。

仅输出一个整数，表示完成目标前提下的最小花费。

样例1输入

2 3 15
2 1
3 2
10 0
20 1
15 0

样例1输出

4

样例1解释

最优方案：选取货物 $0$ 和 $2$，二者均在 $0$ 号仓库，总花费为 $2+2\times 1=4$。

选取货物 $1$ 也刚好能满足要求（$20-3-1\times 2\ge 15$），但花费更多。

单独选取货物 $0$ 或 $2$ 均不能满足要求。

样例2输入

5 3 15
2 1
1 1
3 2
4 2
1 5
10 1
10 1
10 1

样例2输出

3

样例2解释

小 P 所有货物均存放在仓库 $1$ 中，任取两件货物卖出即可满足要求（$10+10-1-2\times 1\ge 15$）。

子任务

$30\%$ 的数据满足：

• $m\le 15$

另有 $40\%$ 的数据满足：

• $a_i\le 20$

全部的数据满足：

• $0<n,m\le 1000$

• $0<b_j,c_j\le 20$

• $0<a_i\le 1000$

• $0<v\le 10^6$ 且保证至少存在一种可满足要求的卖货方案。

题解

待补

时间复杂度：$\mathcal{O}(m\times 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 double
using 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)
#endif

const 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;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。