题解|HDU - 6772

E - Lead of Wisdom | dfs剪枝原题链接

题意：

有n个道具，道具有m个种类，每个种类的道具只能拿一个，每个道具有四个属性值a,b,c,d。同时题目定义了一个价值DMG。

DMG=(100+sum(a))(100+sum(b))(100+sum(c))(100+sum(d))。

sum(x)=你所选中的道具。

现在求怎么拿取道具使DMG价值最大，请输出DMG的最大价值。

做题思路：

由条件可知，代码的运行时间给到了8秒，因此我们可以选择深度搜索dfs，来枚举每种种类的选择情况，将dfs中的每层作为当前的种类,每次往下dfs就是假设选择该件装备往下遍历，dfs的深度就是前往下一个种类，这里可以转化为图表表达，如图1-1: alt 图1-1 dfs演示图

在看过基础图像后，可以得到最原始的dfs图像，代码如下：

//将dfs中的每层作为种类,当处于该种类时,遍历种类的所有可能
//当层数到达m+1时,代表在该选择情况下,所有m种种类都被拿取,比较所有种类的最大值
void dfs(long long step,long long a,long long b,long long c,long long d){
	if (step==m+1)
	{
		maxn=max(maxn,a*b*c*d);
		return ;
	}
    //将a,b,c,d添加上选中的值
	for (Index to:e[step])dfs(step+1,a+to.a,b+to.b,c+to.c,d+to.d); 
}

为什么说上图是最原始的dfs，原因很简单，因为哪怕给到了8秒的时间运行，但如果不进行剪枝的话，以dfs指数级增长的时间复杂度，一样会超时。

dfs时间复杂度计算模版为b^c，b是分支中的最大分支因子，c是dfs深度，因此在本题中时间复杂度是k^(n/k)，当k取3时,时间复杂度达到最大为3^(n/3)，约等于3^16，所以总时间复杂度为10*3^16约等于8秒。

这里给到两个搜到的计算次方和符号转换的网页:

在线次方和开方计算器链接

科学符号转换器

而当装备数量为空时,相当于使dfs多了一层,使时间复杂度再乘以n,所以导致了时间复杂度变为n*10*3^16为400秒。

通过题目样例，我们可以得到，在代码运行的时，可能存在给出了该种类但种类里并没有装备的情况。此时如果在dfs中就可能造成额外的运行时间。

所以，想要减少时间复杂度，就要跳过这些没有装备的种类，具体代码如下：

//因为此时设置的1为起始点,所以从后往前链接节点 
	for (int i=m;i>=0;i--)
	{
		//记当前节点的链接下一个点为i 
		f[i]=id;
		//倘若存在可以选择的值,记录节点 
		if (e[i].size())id=i;
	}

通过预先处理节点，将没有装备的节点与有装备的节点相链接，就可以得到，完整的dfs，即AC代码:

#include<bits/stdc++.h>
#define FAST_READ                        \
    ios::sync_with_stdio(0), cin.tie(0); \
cout.tie(0);
using namespace std;

const int N=1e6+10,M=3e4+10;
long long t,n,m;
struct Index{
	long long a,b,c,d;
};
vector<Index>e[N];
long long f[N];
long long maxn;

//将dfs中的每层作为种类,当处于该种类时,遍历种类的所有可能
//当层数到达m+1时,代表在该选择情况下,所有m种种类都被拿取,比较所有种类的最大值
void dfs(long long step,long long a,long long b,long long c,long long d){
	//当层数达到m+1时,证明所有种类都已经选取完毕 
	if (step==m+1)
	{
		maxn=max(maxn,a*b*c*d);
		return ;
	}
	//当该种类没有装备时，调至下一个有装备的节点 
	if (!e[step].size())dfs(f[step],a,b,c,d);
	//将a,b,c,d添加上选中的值
	else for (Index to:e[step])dfs(step+1,a+to.a,b+to.b,c+to.c,d+to.d); 
}

void solve(){
	//记得maxn也要初始化 
	maxn=-1;
	cin >>n>>m;
	//所有边记得清空 
	for (int i=1;i<=m;i++)e[i].clear();
	for (int i=1;i<=n;i++)
	{
		long long op,a,b,c,d;
		cin >>op>>a>>b>>c>>d;
		e[op].push_back({a,b,c,d});
	}
	//所有种类可能不会同时出现 
	//记m+1为终点 
	int id=m+1;
	//因为此时设置的1为起始点,所以从后往前链接节点 
	for (int i=m;i>=0;i--)
	{
		//记当前节点的链接下一个点为i 
		f[i]=id;
		//倘若存在可以选择的值,记录节点 
		if (e[i].size())id=i;
	}
	//开始深搜 
	dfs(1,100,100,100,100);
	cout <<maxn<<"\n"; 
	return ; 
}

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