P8687tj_2
SamHJD
·
·
题解
P8687 题解
题目传送门
不难看出，此题不是爆搜就是动态规划，而爆搜需要考虑每一种搭配情况，复杂度 O(2^n) 肯定超时。
考虑动态规划，可以发现数据范围很小，并且是搭配类型的，想到状压。
首先设计状态，一共可以设计出两种：
很显然第二种很合理，那么我们来推一下方程。
思考发现，如果直接枚举 i，再找合理的上一种状态，不是很好找。但我们可以通过已经求出来的一种状态，配合另一种状态，来更新新的状态。
设 v[i] 表示第 i 包糖的口味状态，则有：
dp[i|v[j]]=\min(dp[i|v[j]],dp[i]+1)
考虑正确性，因为 $i$ 状态从 $0$ 开始枚举，因此枚举到 $i|v[i]$ 时肯定已经求出 $dp[i]$ 的值，并且是**最优**的。还有一个问题是是否可能重复选了某包糖，如果是，那么肯定这个值不是最优的，因为你买两包同样的糖和只买一包口味不会有新的。
代码：
```cpp
#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;
}
```