题意：
有$n$个物品，$m$个商店，最多可以去$k$个商店。给出每个物品在哪些商店可以买，求买完$n$个物品的最小花费。

思路：
参考claris的博客：https://www.cnblogs.com/clrs97/p/6130145.html

维护$minv[i][j]$代表在大于等于$i$编号的商店中买$j$物品的最小花费。
搜索时候的话就是遍历每一个商店枚举买还是不买（回溯法），维护$pre[i]$数组代表去过的商店中买$j$物品的最小花费。

剪枝的话就俩：

1. 通过$pre$和$minv$可以算出最小的预估值，如果这个值大于当前答案$ans$，就剪掉。
2. 商店进行排序，物品多和相对便宜的商店排在前面（经实践证实优化3000ms）

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cmath>using namespace std;
typedef long long ll;const int maxn = 107;
const int INF = 0x3f3f3f3f;struct Node {int val; //优先级vector<pair<int,int> >vec;bool operator < (const Node &res) const {return val > res.val;}
}a[maxn];int minv[maxn][maxn],pre[maxn],tmp[maxn][maxn];
int n,m,k,ans;void dfs(int x,int y) { //当前在第x个商店，已经选了y个商店int now = 0; //算出来的值for(int i = 1;i <= n;i++) { //遍历每个物品需要的最少价值if(pre[i] == INF) {//pre代表之前选的，now = INF;break;}now += pre[i];}if(now < ans) {ans = now;}int fore = 0; //预估值for(int i = 1;i <= n;i++) {if(pre[i] == INF && minv[x][i] == INF) return; //minv代表这个物品在x与x之后商店可能的最小花费fore += min(pre[i],minv[x][i]);}if(fore >= ans) return;if(y >= k) return;if(x >= m + 1) return;for(int i = x;i <= m;i++) {for(int j = 1;j <= n;j++) {tmp[y][j] = pre[j];}for(int j = 0;j < a[i].vec.size();j++){ //选第i个商店int a1 = a[i].vec[j].first,a2 = a[i].vec[j].second;pre[a1] = min(pre[a1],a2);}dfs(i + 1,y + 1);for(int j = 1;j <= n;j++) { //回溯pre[j] = tmp[y][j];}}
}void init() {ans = INF;for(int i = 1;i <= n;i++) {pre[i] = INF;minv[m + 1][i] = INF;}for(int i = 1;i <= m;i++) {a[i].val = 0;a[i].vec.clear();}
}void solve() {init();for(int i = 1;i <= n;i++) {int x,p,y,q;scanf("%d%d%d%d",&x,&p,&y,&q);a[x].vec.push_back({i,p});a[y].vec.push_back({i,q});a[x].val++;a[y].val++; //物品多和价格便宜的优先放前面if(p < q) a[x].val++;else a[y].val++;}sort(a + 1,a + 1 + m);for(int i = m;i >= 1;i--) { //后i个商店for(int j = 1;j <= n;j++) { //后i个商店购买第j个物品的最小花费minv[i][j] = minv[i + 1][j];}for(int j = 0;j < a[i].vec.size();j++) { //遍历第i个商店的物品int x = a[i].vec[j].first,y = a[i].vec[j].second;minv[i][x] = min(minv[i][x],y);}}dfs(1,0);if(ans == INF) {printf("-1\n");} else {printf("%d\n",ans);}
}int main() {while(~scanf("%d%d%d",&n,&m,&k)) {solve();}return 0;
}