自动搬运

查看原文

来自洛谷，原作者为

	SamHJD .

搬运于2025-08-24 22:41:29，当前版本为作者最后更新于2023-04-04 22:26:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8687 题解

题目传送门

不难看出，此题不是爆搜就是动态规划，而爆搜需要考虑每一种搭配情况，复杂度 $O(2^n)$ 肯定超时。

考虑动态规划，可以发现数据范围很小，并且是搭配类型的，想到状压。

首先设计状态，一共可以设计出两种：

• $dp[i]$ 表示取状态为 $i$ 的几包糖，最多可以凑出的口味数量。这种状态比较麻烦，且结果不是很容易得出。

• $dp[i]$ 表示凑出状态为 $i$ 的口味最少需要几包糖。

很显然第二种很合理，那么我们来推一下方程。

思考发现，如果直接枚举 $i$，再找合理的上一种状态，不是很好找。但我们可以通过已经求出来的一种状态，配合另一种状态，来更新新的状态。

设 $v[i]$ 表示第 $i$ 包糖的口味状态，则有：

$dp[i|v[j]]=\min(dp[i|v[j]],dp[i]+1)$

$dp[i|v[i]]$ 为更新的新状态，$i$ 为已知的状态 $1$，再找一包糖 $j$，更新出 $dp[i|v[i]]$。

考虑正确性，因为 $i$ 状态从 $0$ 开始枚举，因此枚举到 $i|v[i]$ 时肯定已经求出 $dp[i]$ 的值，并且是最优的。还有一个问题是是否可能重复选了某包糖，如果是，那么肯定这个值不是最优的，因为你买两包同样的糖和只买一包口味不会有新的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,m,k,dp[1<<20],v[1<<20];//状压的数组需要开2^n，因为表示的是状态
int main(){
    scanf("%d%d%d",&n,&m,&k);
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for(int i=1;i<=n;++i){
        int h=0,p;
        for(int j=1;j<=k;++j){
            scanf("%d",&p);p--;
            h=h|(1<<p);//这里不能用+，一包糖里可能有多种同一口味的
        }
        dp[h]=1;//这些口味都可以用一包糖解决
        v[i]=h;//记录糖的状态
    }
    for(int i=0;i<(1<<m);++i){//i枚举的是状态，即0～1...11111（m个1）
        for(int j=1;j<=n;++j){
            dp[i|v[j]]=min(dp[i|v[j]],dp[i]+1);//如上
        }
    }
    if(dp[(1<<m)-1]==0x3f3f3f3f) cout<<-1;//搭配不出来
    else cout<<dp[(1<<m)-1];//搭配出来
    return 0;
}