看到数据量直接暴搜启动
/*
* @lc app=leetcode.cn id=638 lang=cpp
*
* [638] 大礼包
*/
#include <bits/stdc++.h>
#include <csignal>
using namespace std;
// @lc code=start
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special,
vector<int>& needs) {
int n = needs.size();
vector<vector<int>> a;
map<vector<int>, int> mp;
for (auto& x : special) {
bool f = true;
for (int j = 0; j < n; ++j) {
if (x[j] > needs[j]) {
f = false;
break;
}
}
if (f) a.push_back(x);
}
auto dfs = [&](auto&& self, vector<int> cur) -> int {
if (!mp.count(cur)) {
int mi = 0;
for (int i = 0; i < n; ++i) mi += cur[i] * price[i];
for (auto& x : a) {
int sp = x[n];
vector<int> next;
for (int i = 0; i < n; ++i) {
if (x[i] > cur[i]) break;
next.emplace_back(cur[i] - x[i]);
}
if (next.size() == n) {
mi = min(mi, self(self, next) + sp);
}
}
mp[cur] = mi;
}
return mp[cur];
};
return dfs(dfs, needs);
}
};
// @lc code=end