1921: 蓝桥杯算法提高VIP-金陵十三钗

dfs

不剪枝的话会有3个点超时

#include<bits/stdc++.h>
using namespace std;
int like[105][105];
int stu[105]; 
int maxn[105];
int ans=0;
int n;
void dfs(int i,int j,int num)
{
	if(j==n)
	{
		return;
	}
	if(i==n)
	{
		ans=max(ans,num);
		return;
	}
	if(stu[j]==0&&num+((n-i-1)*100+like[i][j])>ans)//剪枝,假如还没选的人都是与学生一模一样的（100）还没当前最好相似度大的话就不选.
	{
		stu[j]=1;
	    dfs(i+1,0,num+like[i][j]);//选择当前学生
	    stu[j]=0;
	}
	dfs(i,j+1,num);//不选当前学生
	
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf("%d",&like[i][j]);
		}
	}
	dfs(0,0,0);
	printf("%d",ans);
	return 0;
}