※ 引述《ledia (contemplation)》之铭言： : ※ 引述《kc655039 (￾NN￾N ￾  )》之铭言： : 的确不是很容易看 ^^; : 在还没看完你的程式码之前 : 说实在我也不太知道该怎麽帮你的程式加速 : 不过我自己写这题的经验上看来 : 或许你是多做了太多重覆的事情 : 因为我的程式用了 1.820 秒(虽然也不少了), 而这题限 10 秒 过了也差不多有半年了,最近又开始写这题,想说也过了半年了....之类的, 跟上回用的方法一样,可是发现递回似乎可以用一下,所以就用了,想说搞不 好会有令人高兴的结果,一开始还是TLE,TLE了满多次不管我怎麽改都一样, 後来发现....是因为下面红色字的地方本来是零,Backtracking(...)的参数 本来也没有k,改成现在这样以後就很快的AC了(0:00:340),然後其实之前就 想说如果第一个或是其中有一个没办法构成边其实就是no了,所以就一开始 就放存放边的array的第一个元素进去,这样就可以减少递回树的size, 改了这样以後就变成0:00:076,後来又想,如果由小到大排列,这样的话, 如果加上某边然後就大於边长,那後面的边都可以不用试了,也可以减少递回 的次数,所以我就上了,可是还是0:00:076....是因为排列把时间拖回来了吗?? 还是排列的时机不对之类的,所以目前就这样了...我似乎想不出加速的方法了, 不过真的令我满惊讶的,想不到把红字的地方做那样的改变会差那麽多..... 还是有点搞不懂...是哪种侧资会差到从TLE到000340..... 对了请你把你的code寄给我好吗 [email protected] 我想多看看, 下面是code应该比以前那个好看满多百倍的了吧.是没有排序的. 不过好像还是满难看的所以加了些注解,递回树的size好像决定了速度?? 还有就是我有用到一个全域变数judge那个可以不用吗,因为有时候用递回, 都会用全域变数,我在想说有没办法完全不要用这样. #include <iostream> using std::cout; using std::cin; using std::endl; int judge; void Backtracking(int k,const int length,int n,int data[][20],int total,int accumulator) { int i; if (accumulator>length) return; if (total==3) { judge=1; return; } if (accumulator==length) { for (i=0;i<n;i++)//这个主要是放下一个边的第一个元素 if (data[1][i]) { data[1][i]--; Backtracking(i,length,n,data,total+1,data[0][i]); data[1][i]++; break; } return; } for (i=k;i<n;i++) { if (data[1][i]) { data[1][i]--; Backtracking(i,length,n,data,total,accumulator+data[0][i]); if (judge) break; data[1][i]++; } } } main() { int N; int n; int data[2][20];//存放资料的地方上层是存边长,下层存有几个这个长度 //的资料 int length; //边长 int i,j,temp,counter,yes; cin>>N; while (N) { length=0; judge=0; counter=0; yes=0; cin>>n; for (i=0;i<n;i++)//这个回圈主要用来输入资料,顺便整理 { cin>>temp,length+=temp; for (j=0;j<counter;j++) if (temp==data[0][j]) { data[1][j]++; break; } if (j==counter) data[0][counter]=temp,data[1][counter++]=1; }//counter是资料的数量 if (length%4==0) { length/=4;//算一下一个边多长这样 for (i=0;i<counter;i++)//看看有没有输入的资料大於边长 if (data[0][i]>length) { yes=1; break; } if (!yes) { data[1][0]--; Backtracking(0,length,counter,data,0,data[0][0]); } } if (judge) cout<<"yes"<<endl; else cout<<"no"<<endl; N--; } return 0; } --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.161.12.54 ※ 编辑: kc655039 来自: 218.161.12.54 (02/19 21:05)