2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——M. Web Delivery（采用 naive if else方法，应用不同状态压缩方法，解决该问题）（枚举一个 S 的子集的子集方法）（利用乘积约束） · znzryb
## 题目大意
**题目描述**
Gagamboy 需要购买 $r$ 种不同的化学物质，每种需要 1kg。电商平台上共有 $c$ 个卖家。
给定一个 $r \times c$ 的价格矩阵 $A$，其中 $a_{i,j}$ 表示从卖家 $j$ 处购买 1kg 化学物质 $i$ 的价格。
此外，对于每个卖家 $j$，只要从该卖家处购买了任何数量的化学物质（哪怕只有一种），都**需要额外支付一笔固定的配送费** $d_j$。
**请计算购买到所有** $r$ **种化学物质（每种至少 1kg）所需的最小总花费**。本题包含多组独立测试数据。
**输入格式**
第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。
对于每组测试数据：
第一行包含两个由空格分隔的整数 $r$ 和 $c$（$1 \le r, c$，且 $r \times c \le 250$）。
接下来 $r$ 行，每行包含 $c$ 个由空格分隔的整数，第 $i$ 行的第 $j$ 个数为 $a_{i,j}$（$1 \le a_{i,j} \le 10^{15}$）。
最后一行包含 $c$ 个由空格分隔的整数 $d_1, d_2, \dots, d_c$（$1 \le d_j \le 10^{15}$），表示每个卖家的配送费。
**输出格式**
对于每组测试数据，输出一行一个整数，表示完成购买所需的最小总花费。
**样例输入**
```
2
3 5
1 3 5 7 9
5 7 9 1 3
9 1 3 5 7
4 3 2 3 4
4 3
1 2 4
2 3 1
4 1 2
3 2 1
2 4 4
```
**样例输出**
```
11
11
```
**样例解释**
对于第一组样例：
一种最优的购买方案如下：
- 向卖家 2 购买化学物质 1 和 3。它们的价格分别为 $a_{1,2} = 3$ 和 $a_{3,2} = 1$。支付这笔订单所需的配送费为 $d_2 = 3$。
- 向卖家 4 购买化学物质 2。它的价格为 $a_{2,4} = 1$。支付这笔订单所需的配送费为 $d_4 = 3$。
总花费为：$((3 + 1) + 3) + (1 + 3) = 11$。
对于第二组样例：
最优方案能达到的最小花费同样为 11。
## 思路讲解
这道题目的做法，首先，需要想到：绷不住了，这道题目，观察到 chem * sell <= 250，那么，chem，sell 理论上来说，应该不会同时超过 16，因为 16*16=256，这样子，**chem 小，就对 chem 进行状态压缩**，**sell 小，就对 sell 进行状态压缩**。
确实是感觉到，**如果不进行状态压缩，那么这道题目非常难做**。
如果进行状态压缩的话，状态压缩 seller 非常好做。**枚举的是给哪些 seller 付了这个运费。**
**给哪些 seller 付了这个运费，就只能从这些 seller 这里购买化学品。**
```cpp
ll ans=INF;
// 枚举的是给哪些 seller 付了这个运费
for (int s=1;s<(1<<M_j_sell);++s) {
vector<ll> mn_price(N_i_chem+2,INF);
ll offset_j=1;
ll price=0;
// 给哪些 seller 付了这个运费，就只能从这些 seller 这里购买化学品
for (int j=0;j<M_j_sell;++j) {
if (s>>j&1) {
price+=D_j_sell[j+offset_j];
for (int i=1;i<=N_i_chem;++i) {
mn_price[i]=min(mn_price[i],A[i][offset_j+j]);
}
}
}
for (int i=1;i<=N_i_chem;++i) {
price+=mn_price[i];
}
ans=min(ans,price);
// dp[s]=price;
}
cout<<ans<<"\n";
```
我们来看，**状态压缩 chem**，我们怎么做？这个会难一点。
我们不难观察到，一个子集 S 的最优解，一定是这样的：**把一部分子集交给一个买家，把另一部分子集交给一个买家，把又一部分子集交给又一买家**……。
在状态压缩 化学品的时候，我们需要学习一种写法，即枚举 mask 的子集。
```cpp
for (int S = 0; S < (1 << r); S++) {
for (int T = S; T > 0; T = (T - 1) & S) {
// T 是 S 的非空子集
dp[S] = min(dp[S], dp[S ^ T] + best[T]);
}
}
```
枚举 mask 的所有子集，是 $O(3^n)$。
如果说枚举 seller，允许你去这个枚举子集，是不是会简单一点？
**预处理**：对每个非空子集 $T$，预先算好从所有卖家中买 $T$ 的最小花费：best（T）的意思就是在包括这个运费的情况下，**该 chem 子集 T，从哪一个买家那里采购，所需花费最低**？
$$
\text{best}(T) = \min_{j=1}^{c} \left(d_j + \sum_{i \in T} a_{i,j}\right)
$$
具体而言就是：
```cpp
ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
ll lans=INF;
for (int j=1;j<=M_j_sell;++j) {
ll price=D_j_sell[j];
for (int i=0;i<N_i_chem;++i) {
if (s>>i&1) {
price+=A[offset_i+i][j];
}
}
lans=min(lans,price);
}
best[s]=lans;
}
```
转移方程如下，容易写出：
$$
dp[S] = \min_{\emptyset \neq T \subseteq S} \left(dp[S \setminus T] + \text{best}(T)\right)
$$
你可能会有疑问，**这个运费会不会重复算**？答案是是的，**但是我们肯定不会采用运费重复算的组合**。
```cpp
vector<ll> dp((1<<N_i_chem)+2);
// for (int j=1;j<=M_j_sell;++j) {
// dp[0][j]=0;
// }
// for (int s=1;s<(1<<N_i_chem);++s) {}
ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
ll lans=INF;
for (int j=1;j<=M_j_sell;++j) {
ll price=D_j_sell[j];
for (int i=0;i<N_i_chem;++i) {
if (s>>i&1) {
price+=A[offset_i+i][j];
}
}
lans=min(lans,price);
}
best[s]=lans;
}
for (int s=1;s<(1<<N_i_chem);++s) {
ll lans=INF;
for (int t=s;t>0;t=(t-1)&s) {
lans=min(lans,dp[s^t]+best[t]);
}
dp[s]=lans;
}
cout<<dp[(1<<N_i_chem)-1]<<"\n";
```
## AC代码
AC
[https://codeforces.com/gym/106262/submission/365538444](https://codeforces.com/gym/106262/submission/365538444)
::: 源代码
```cpp
/**
* Problem: M. Web Delivery
* Contest: 2025 ICPC Asia Manila Regional
* Judge: Codeforces
* URL: https://codeforces.com/gym/106262/problem/M
* Created: 2026-03-05 14:02:59
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N_i_chem,M_j_sell;
cin >> N_i_chem >> M_j_sell;
vector<vector<ll>> A(N_i_chem+2,vector<ll>(M_j_sell+2));
for (int i=1;i<=N_i_chem;++i) {
for (int j=1;j<=M_j_sell;++j) {
cin>>A[i][j];
}
}
vector<ll> D_j_sell(M_j_sell+2);
for (int j=1;j<=M_j_sell;++j) {
cin>>D_j_sell[j];
}
// 绷不住了，这道题目，观察到 chem * sell <= 250
// 那么，chem，sell 理论上来说，应该不会同时超过 16，因为 16*16=256
// 这样子，chem 小，就对 chem 进行状态压缩
// sell 小，就对 sell 进行状态压缩
if (N_i_chem<=M_j_sell) {
vector<ll> dp((1<<N_i_chem)+2);
// for (int j=1;j<=M_j_sell;++j) {
// dp[0][j]=0;
// }
// for (int s=1;s<(1<<N_i_chem);++s) {}
ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
ll lans=INF;
for (int j=1;j<=M_j_sell;++j) {
ll price=D_j_sell[j];
for (int i=0;i<N_i_chem;++i) {
if (s>>i&1) {
price+=A[offset_i+i][j];
}
}
lans=min(lans,price);
}
best[s]=lans;
}
for (int s=1;s<(1<<N_i_chem);++s) {
ll lans=INF;
for (int t=s;t>0;t=(t-1)&s) {
lans=min(lans,dp[s^t]+best[t]);
}
dp[s]=lans;
}
cout<<dp[(1<<N_i_chem)-1]<<"\n";
}else {
// vector<ll> dp((1<<M_j_sell)+2);
ll ans=INF;
for (int s=1;s<(1<<M_j_sell);++s) {
vector<ll> mn_price(N_i_chem+2,INF);
ll offset_j=1;
ll price=0;
for (int j=0;j<M_j_sell;++j) {
if (s>>j&1) {
price+=D_j_sell[j+offset_j];
for (int i=1;i<=N_i_chem;++i) {
mn_price[i]=min(mn_price[i],A[i][offset_j+j]);
}
}
}
for (int i=1;i<=N_i_chem;++i) {
price+=mn_price[i];
}
ans=min(ans,price);
// dp[s]=price;
}
cout<<ans<<"\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106262/submission/365538444
*/
```
:::
## 心路历程（WA，TLE，MLE……）