TLE0pts求调

P3799 小 Y 拼木棒

您这纯枚举确实太慢了,四层循环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


|