2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——M. Web Delivery（采用 naive if else方法，应用不同状态压缩方法，解决该问题）（枚举一个 S 的子集的子集方法）（利用乘积约束）

题目大意

题目描述
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 这里购买化学品。

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 的子集。

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)$$

具体而言就是：

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)$$

你可能会有疑问，这个运费会不会重复算？答案是是的，但是我们肯定不会采用运费重复算的组合。

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

源代码

/**
 * 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……）