[数据结构与算法][Acwing|蓝桥] 1243. 糖果 状态压缩+01背包

前言

传送门 :

思路

因为数据范围很小, 我们考虑使用 $dp$

显然对于每袋 糖果 有 拿和不拿两种状态 , 所以需要使用 背包

同时,又因为 需要 表示当前状态 ,所以考虑使用 状态压缩

状态表示 :
$dp[N][1<<M]$ 表示 从前$i$袋糖果选,状态为$s$的最小集合

状态计算 :
$dp[i][s]=min(dp[i][s],dp[i?1][s\&(?w[i])]+1)(?w[i]表示按位取反,Latex打不出来$

因为$N=100$ ,因为空间开销$2^{20}?N$ 会寄

所以考虑优化$1$维,当然我们跟着 背包 倒序转移即可

Mycode

// Problem: 糖果
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1245/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 110,M  =(1<<20)+10 , INF = 0x3f3f3f3f;
int w[N],f[M],n,m,k;

void solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			int x;cin>>x;
			w[i]|=  1<<x-1;
		}
	}
	
	memset(f,0x3f,sizeof f);
	f[0] = 0 ;
	for(int i=1;i<=n;i++)
		for(int s = (1<<m);s>0;s--)
		f[s] = min(f[s],f[s&(~w[i])]+1);
		
	if(f[(1<<m)-1] == INF)cout<<-1<<endl;
	else cout<<f[(1<<m)-1]<<endl;
	
}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读