求大佬帮忙看看怎么优化下
查看原帖
求大佬帮忙看看怎么优化下
254321
胡萝卜兔楼主2020/8/25 02:30

后五个点全部TLE,代码如下

#include <iostream> 
#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
int n,m,a[25],v[25],ans[25];
int b[25],maax=-1;
set<int>s;
void choose()
{
	for(int i=1;i<n-m+1;i++)
	{
		b[i-1]=a[ans[i]];//选完后的数存到数组b里
	}
	s.clear();
	int k=n-m;
	int sum=0;
	for(int i=0;i<(1<<k);i++)
	{//二进制枚举
		sum=0;
		for(int j=0;j<k;j++)
		{
			if(i&(1<<j))
			{
				sum=sum+b[j];
			} 
		}
		if(sum!=0)
			s.insert(sum);
	}
	int x=s.size();
	maax=max(x,maax);	
} 
void dfs(int p,int q)
{
	if(q==n-m+1)
	{
		choose();//选中了n-m个,角标进行筛选存在了ans数组里
		return ; 
	}
	for(int i=p;i<=n;i++)
	{
		if(v[i]==0)
		{
			v[i]=1;
			ans[q]=i;
			dfs(i+1,q+1);
			v[i]=0;
		}
	}
	return ; 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs(1,1);
	cout<<maax;
	return 0;
}
2020/8/25 02:30
加载中...