CSP 第34次认证第四题货物调度

本文主要是介绍CSP 第34次认证第四题货物调度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

只想做一个30分解法。考场上写dfs只能过15分，不思其解。系统未开放评测。
将复现方法粘贴如下，开放数据后再进行测试。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;int n, m, v;
struct store {int b, c;
};
struct Goods {int a, t;
};
store Store[1010];
Goods goods[1010];int ans = 0x3f3f3f3f;bool flag[1010];// 标记每个物品时选择了还是没有选择void dfs(int u, int sum) {if (u == m) {// 遍历完了m个物品// 求一下cost,需要知道每个选择的物品是哪个仓库的，goods.t 就是。还要知道每个仓库一共调用了多少物品map<int, int>count;for (int i = 0; i < m; i ++ ) {if (flag[i]) // 选择了第i个货物count[goods[i].t] ++;}int cost = 0;for (auto [key, value]: count) {// key: count.first, value: count.second;int basic = Store[key].b;int add = Store[key].c;cost += basic + add * value;}if (sum - cost >= v) {ans = min(ans, cost);}return ;}// 不选择 dfs(u + 1, sum);// 选择 uflag[u] = 1;dfs(u + 1, sum + goods[u].a);flag[u] = 0;}int main() {cin >> n >> m >> v;for (int i = 0; i < n; i ++ ) {cin >> Store[i].b >> Store[i].c;}for (int i = 0; i < m; i ++ ) {cin >> goods[i].a >> goods[i].t;}// 解决 m = 15 的情况，每个物品选择还是不选择 dfs(0, 0); // 从第0个物品开始，已经选择的货物获得的现金为0cout << ans << endl;return 0;
}