dzm

用户名：17160200112

访问量：33945

签　名：

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

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

蓝桥杯算法提高VIP-金陵十三钗-题解（C++代码）

　　作者: dzm　　　　发表时间：2020-07-16 17:47:57 浏览：321　|　评论：0　

原题链接：蓝桥杯算法提高VIP-金陵十三钗

未优化版本
看到数据不大，以为能过，结果时间超限73% 
```
#include <iostream>
using namespace std;

int n;
int a[1005][1005];
int row[1005];
int maxn=-1e8;

void dfs(int x,int sum)
{
	if(x>n)
	{
		maxn=max(maxn,sum);
		return; 
	}
	for(int i=1;i<=n;i++)
	{
		if(row[i]==0)
		{
			row[i]=1;
			dfs(x+1,sum+a[x][i]);
			row[i]=0;
		}
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) 
			cin>>a[i][j];
	dfs(1,0);
	cout<<maxn;
	return 0;
}
```
看了别人的解法后，加上剪枝才AC
优化版本
```
#include <iostream>
using namespace std;

int n;
int a[1005][1005];
int row[1005];
int maxn=-1e8;
int m[1005];

void dfs(int x,int sum)
{
	if(x>n)
	{
		maxn=max(maxn,sum);
		return; 
	}
	for(int i=1;i<=n;i++)
	{
		if(row[i]==0&&m[x]+sum>maxn)
		{
			row[i]=1;
			dfs(x+1,sum+a[x][i]);
			row[i]=0;
		}
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) 
			cin>>a[i][j];
	for(int i=n;i>=1;i--)
	{
		int maxnn=-1e8;
		for(int j=1;j<=n;j++)
		{
			maxn=max(maxn,a[i][j]);
		}
		m[i]=m[i+1]+maxn; 
	}
	dfs(1,0);
	cout<<maxn;
	return 0;
}
```

0.0分

3 人评分

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

dzm

TA的其他文章

你可能喜欢

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

上车人数（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C二级辅导-统计字符（C语言代码）

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

蓝桥杯算法提高VIP-金陵十三钗-题解（C++代码）

评论区

精彩推荐

Tom数（C++代码）

川哥的吩咐（C++代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

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

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

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

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

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

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

母牛的故事（C语言代码）

dzm

TA的其他文章

你可能喜欢

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

上车人数 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

C二级辅导-统计字符 （C语言代码）

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

蓝桥杯算法提高VIP-金陵十三钗-题解（C++代码）

评论区

精彩推荐

Tom数 （C++代码）

川哥的吩咐 （C++代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

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

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

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

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

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

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

母牛的故事 （C语言代码）

上车人数（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C二级辅导-统计字符（C语言代码）

　　评论区

Tom数（C++代码）

川哥的吩咐（C++代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

母牛的故事（C语言代码）