由于范围比较小,n就100个所以直接n^3就可以处理了
这里直接枚举从每一头奶牛作为爆炸源点的情况
太菜了不会将map内全变为1只能循环赋值了,但不影响大体时间复杂度,还是n^3
由于当一头奶牛影响了多头奶牛时,我们需要先记录这些奶牛,然后最后一起传递下一层
(感觉有点像bfs但是大体结构上还是dfs嘛就认为它是dfs了O(∩_∩)O哈哈~)
ps:有一个小坑就是,st数组要开内部,否则上个传递的情况将会改变st数组,debug了好久
#include<iostream>
#include<map>
#include<cmath>
#include<cstring>
using namespace std;
const int N=110;
int g[N];
map<int ,int >mp;
int n,res;
int dfs(int u,int x)
{
int m=0,q=1;
int st[N];
for(int i=1;i<=n;i++)
{
if(abs(g[i]-x)<=u&&mp[g[i]]==1)
{
st[m++]=g[i];
mp[g[i]]=0;
}
}
for(int i=0;i<m;i++)
{
//这里st数组内容变了
q+=dfs(u+1,st[i]);
}
return q;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>g[i];
mp[g[i]]=1;
}
for(int i=1;i<=n;i++)
{
mp[g[i]]=0;
res=max(res,dfs(1,g[i]));
for(int j=1;j<=n;j++)mp[g[j]]=1;
}
cout<<res;
return 0;
}