【题解】导游-C++

绝地灬酷狼 2021-10-18 07:58 291阅读 0赞

Description  
宁波市的中小学生们在镇海中学参加程序设计比赛之余，热情的主办方邀请同学们参观镇海中学内的各处景点，已  
知镇海中学内共有n处景点。现在有n位该校的学生志愿承担导游和讲解任务。每个学生志愿者对各个景点的熟悉程  
度是不同的，如何将n位导游分配至n处景点，使得总的熟悉程度最大呢？要求每个景点处都有一个学生导游。  
Input  
有若干行：  
第一行只有一个正整数n(1≤n≤17)，表示有n个景点和n个学生导游。  
第二行至第n+1行共n行，每行有n个以空格分隔的正整数。  
第i+1行的第j个数k(1≤k≤1000)，表示第i个学生导游对景点j的熟悉程度为k。  
Output  
只有一行，该行只有一个正整数，表示求得的熟悉程度之和的最大值。  
Sample Input  
3  
10 6 8  
9 2 3  
1 7 2  
Sample Output  
24  
//第1个学生负责第3个景点，第2个学生负责第1个景点，第3个学生负责第2个景点时，熟悉程度总和为24，达到最大值

这道题目是一道极大化剪枝。  
很明显，这道题目用我们的爆搜大法好 是AC不了的。  
为什么呢？  
每个景点的选择情况有n种，共n个景点，爆搜的时间复杂度到了O(n^n)，而n最大为17，这尼玛绝对TLE.  
我们先**开挂** 把可能得到的最大熟悉度算出来（因为开了挂所以一个人可以负责很多景点）  
然后在搜索过程中！运用这个开挂值awa，如果当前状态，加上后面的开挂值如果比总开挂值还要大（我也不知道为什么会有这种情况）那这种情况就要剪枝。  
虽然不知道为什么但是这原理非常简单，**如果当前值以及以后的极大值的和比全局极大值还要大，这种情况就应该剪掉**！  
其他的和爆搜没什么区别，爆搜的实现也还算简单，下面就直接贴代码，**摸鱼酱的代码没有注释觉得好请点赞**.

#include<bits/stdc++.h>
    using namespace std;
    int n,d[20][20],dis[20];
    bool flag[20];
    int ans=-1;
    void dfs(int dep,int sum)
    {
    	if(dep==n+1)
    	{
    		ans=max(ans,sum);
    		return;
    	}
    	if(ans>=sum+dis[n]-dis[dep-1])return;
    	for(int i=1;i<=n;i++)
    	{
    		if(!flag[i])
    		{
    			flag[i]=1;
    			dfs(dep+1,sum+d[dep][i]);
    			flag[i]=0;
    		}
    	}
    	return;
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		int m=-1;
    		for(int j=1;j<=n;j++)
    		{
    			cin>>d[i][j];
    			m=max(m,d[i][j]);
    		}
    		dis[i]=dis[i-1]+m;
    	}
    	dfs(1,0);
    	cout<<ans<<endl;
    	return 0; 
    }

ov.

转载于:https://www.cnblogs.com/moyujiang/p/11167724.html