1243. 糖果

题目链接

1243. 糖果

糖果店的老板一共有 \(M\) 种口味的糖果出售。

为了方便描述，我们将 \(M\) 种口味编号 \(1～M\)。

小明希望能品尝到所有口味的糖果。

遗憾的是老板并不单独出售糖果，而是 \(K\) 颗一包整包出售。

幸好糖果包装上注明了其中 \(K\) 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 \(N\) 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入格式

第一行包含三个整数 \(N,M,K\)。

接下来 \(N\) 行每行 \(K\) 这整数 \(T_1,T_2,???,T_K\)，代表一包糖果的口味。

输出格式

一个整数表示答案。

如果小明无法品尝所有口味，输出 \(?1\)。

数据范围

\(1≤N≤100,\)
\(1≤M,K≤20,\)
\(1≤T_i≤M\)

输入样例：

输出样例：

解题思路

状压dp

很显然的状压dp：

状态表示：\(f[i][j]\) 表示前 \(i\) 包糖果，状态为 \(j\) 时的最少糖果包数
状态计算：
- \(f[i][j|a[i]]=min(f[i][j|a[i]],f[i-1][j]+1)\)
- \(f[i][j]=min(f[i][j],f[i-1][j])\)
  分析：对于第 \(i\) 个物品有选和不选两种情况，都由 \(f[i-1][j]\) 转移过去，注意不选的情况不能漏

时间复杂度为 \(1e8\)，得加 \(O2\) 优化才能过，另外数组滚动为一维后不需要

IDA*

可以算是经典问题，重复覆盖问题，即给定一个矩阵，选定最少的行使所有的列都会被覆盖。
不妨先考虑暴搜：枚举列，选择包含该列的行，一层一层枚举，这样所有的情况都包含了，可以考虑一些剪枝：

\(ID\)：即迭代加深。逐层判断：一行，两行，三行……是否能完全覆盖列
选择可选情况少的，即选择可选情况最少的列，这样感性上来说可较快搜索到答案
\(A*\)。即估价函数。设计一个估价函数 \(h(state)\) 表示状态为 \(state\) 时至少还需要多少行。首先，这样一种方案肯定是允许的，对于某一列，将其所有行都选掉，这样不一定是最优的，但将该列的所有行当作一行时，这样正确结果就不会比这些选出的行数还小

时间复杂度：\(O(n\times 2^m)\)

代码

状压dp

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")


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

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int n,m,k,a[105],f[2][1<<21];
int main()
{
    read(n),read(m),read(k);
    for(int i=1;i<=n;i++)
	{
		int x=0;
    	for(int j=1;j<=k;j++)
    	{
    	    int y;
    	    read(y);
    	    y--;
    	    x|=(1<



滚动数组

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

// %%%Skyqwq
#include 
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int n,m,k,a[105][25],b[105],f[1<<21];
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=k;j++)
    	{
    		cin>>a[i][j];
    		a[i][j]--;
    	}
    for(int i=1;i<=n;i++)
    {
    	int x=0;
    	for(int j=1;j<=k;j++)
    		x|=(1<


IDA*

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

// %%%Skyqwq
#include
#include
#include
#include
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105,M=1<<20;
int log2[M],n,m,k;
vector col[N];
int h(int state)
{
	int res=0;
	for(int i=(1<depth)return state==(1<col[c].size())t=c;
	}
	for(auto row:col[t])
		if(dfs(depth-1,state|row))
			return true;
	return false;
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i>x;
    		x--;
    		state|=1<>j&1)
    			col[j].pb(state);
    }
    int depth=0;
    while(depth<=m&&!dfs(depth,0))depth++;
    cout<<(depth>m?-1:depth);
    return 0;
}


						
							

						
							
							
			蓝桥杯dfs变形状压DPIDA


					
					
					
						相关
						
				
						
			
																
								
										蓝桥杯历年真题你刷了吗？过来人教你逆袭！
									
									
								 

        
								
							
							

																
								
										[蓝桥杯2016初赛]剪邮票
									
									
								 

        
								
							
							

																
								
										【蓝桥杯】第十二届蓝桥杯砝码称重（Python题解）
									
									
								 

        
								
							
							

																
								
										蓝桥杯真题 时间显示
									
									
								 

        
								
							
							

																
								
										蓝桥杯 猜生日
									
									
								 

        
								
							
							

																
								
										蓝桥杯 阶乘计算
									
									
								 

        
								
							
							

																
								
										蓝桥杯--数的分解（c语言解法）
									
									
								 

        
								
							
							

																
								
										蓝桥杯--数列求值
									
									
								 

        
								
							
							

																
								
										第十一届蓝桥杯JavaB组题目及部分题解
									
									
								 

        
								
							
							

																
								
										0103 最短Hamilton路径(状压DP)
									
									
								 

        
								
							
							

																
								
										蓝桥杯 --- (费解的开关)
									
									
								 

        
								
							
							

																
								
										蓝桥杯 直线

1243. 糖果

题目链接

1243. 糖果

输入格式

输出格式

数据范围

输入样例：

输出样例：

解题思路

代码

相关

蓝桥杯历年真题你刷了吗？过来人教你逆袭！

[蓝桥杯2016初赛]剪邮票

【蓝桥杯】第十二届蓝桥杯砝码称重（Python题解）

蓝桥杯真题时间显示

蓝桥杯猜生日

蓝桥杯阶乘计算

蓝桥杯--数的分解（c语言解法）

蓝桥杯--数列求值

第十一届蓝桥杯JavaB组题目及部分题解

0103 最短Hamilton路径(状压DP)

蓝桥杯 --- (费解的开关)

蓝桥杯直线

标签