求助dfs
查看原帖
求助dfs
684866
wangborui123楼主2024/10/27 11:47

rt,考场上这么写的,以为能骗4个点,结果回家一测全TLE

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int a[N],n,b[N],ans,cnt;
void check()
{
	int res=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i-1;j>0;j--)
		{
			if(b[i]!=b[j] and a[i]==a[j])res+=a[i];
		}
	}cnt=res;
}
void dfs(int k,int res)
{
	b[k]=res;check();ans=max(ans,cnt);
	for(int i=k+1;i<=n;i++)
	{
		dfs(i,0);dfs(i,1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int T;cin>>T;
	while(T--)
	{
		ans=0,cnt=0;
		cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
		dfs(0,0);
		cout<<ans<<"\n";
	}
	cout<<endl;
	return 0;}
2024/10/27 11:47
加载中...