您这纯枚举确实太慢了,四层循环n^4的复杂度啊
建议剪枝深搜,一般的深搜会超时
这里是我的代码,dfs超时0pts,也许可以参考一下dfs的写法(这个是暴力深搜)
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
long long n,tot;
int sti[100010];
bool vis[100010];
int tri[5];
long long const int big=10000000007;
int youmu(int k){
for(int i=k;i<=n;i++){
if(vis[i]==false){
tri[k]=sti[i];
vis[i]=true;
sort(tri,tri+k);
//测试代码头,输出当前组合
// for(int j=1;j<=k;j++){
// cout<<tri[j]<<' ';
// }
// cout<<"\n";
//测试代码尾
if(k==4&&tri[1]+tri[2]==tri[3]&&tri[1]+tri[2]==tri[4]){
tot++;
// add[k]=tri[4];
}
else{
youmu(k+1);
}
vis[i]=false;
}
}
if(k=-1){
return 0;
}
}
int main(){
//输入数据
cin>>n;
for(int i=1;i<=n;i++){
cin>>sti[i];
}
if(n<4){
cout<<0;
return 0;
}
//初始化数组
//memset(vis,false,sizeof(vis));
youmu(1);
cout<<tot%big;
return 0;
}
```
这个取余可能需要边枚举边取余,但考虑到本题是枚举数学,可以用数学相关知识结合深搜进行剪枝。
暂时没研究剪枝,但是应该能剪。
by Hakurei06 @ 2024-03-30 19:28:35
@[Hakurei06](/user/815833)
刚才看了一下,这题不好剪枝
建议考虑动规,动规啊万能的动规,动门(
by Hakurei06 @ 2024-03-30 19:33:51
有个新方法,详见我那帖罢(
虽然我还没试过但是应该O=n²是能过的
by Hakurei06 @ 2024-03-30 19:47:47