dzm

用户名：17160200112

访问量：33947

签　名：

等　　级
排　　名	68
经　　验	10353
参赛次数	0
文章发表	172
年　　龄	0
在职情况	学生
学　　校	大连东软信息学院
专　　业	电子信息工程

　　自我简介：

TA的其他文章

蓝桥杯2015年第六届真题-打印大X-题解（C++代码）
浏览：266

蓝桥杯2018年第九届真题-次数差-题解（C++代码）
浏览：225

蓝桥杯2018年第九届真题-等腰三角形-题解（C++代码）
浏览：833

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

蓝桥杯算法训练VIP-邮票-题解（C++代码）dfs

　　作者: dzm　　　　发表时间：2020-06-27 18:15:44 浏览：196　|　评论：0　

原题链接：蓝桥杯算法训练VIP-邮票

未优化前用记忆化搜索，时间会超时,只能过67%
```
#include <iostream>
using namespace std;

int a[105];
int vis[105];
int map[25505];
int n,m;

void dfs(int x,int sum,int c)
{
	map[sum]=1;
	if(x>n) return;
	for(int i=x;i<=n;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;
			for(int j=c;j<=m;j++)
			{
				dfs(i+1,sum+a[j],j);
				vis[i]=0;
			}
		}
	}
}

int main()
{
	cin>>n;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		map[a[i]]=1;
	}
  	dfs(1,0,1);
	for(int i=1;i<=25505;i++)
	{
		if(map[1]==0) 
		{
			cout<<0;break;  
		} 
		if(map[i]==0)
		{
			cout<<i-1;
			break;
		}	
	}
	return 0;
}
```
看了别人写的题解后才发现我写的多了一层没有必要的for循环(加了这层循环相当于重复好多次，自然也就会超时了)。仔细思考后才反应过来这个贴邮票没有位置关系，不需要去搜索枚举每个位置，这个只是统计了总的贴了邮票的值。
优化：去掉多余的for循环，这样也就不需要去记忆化标记了。
```
#include <iostream>
using namespace std;

int a[105];
int map[25505];
int n,m;

void dfs(int x,int sum,int cnt)
{
	map[sum]=1;
	if(x>n) return;
 
	for(int j=cnt;j<=m;j++)
	{
		dfs(x+1,sum+a[j],j);
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		map[a[i]]=1;
	}
  	dfs(1,0,1);
  	for(int i=1;i<=25505;i++)
  	{
		if(map[1]==0) 
		{
			cout<<0;break;  
		} 
		if(map[i]==0)
		{
			cout<<i-1;break;
		}	
  	}
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

dzm

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

台球碰撞（C++代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

蓝桥杯算法训练VIP-邮票-题解（C++代码）dfs

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

多输入输出练习1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

DNA （C语言描述，数据结构）

dzm

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

台球碰撞 （C++代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

十->二进制转换 （C++代码）（零和负数需要特殊处理）

蓝桥杯算法训练VIP-邮票-题解（C++代码）dfs

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

多输入输出练习1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

DNA （C语言描述，数据结构）

台球碰撞（C++代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

　　评论区