2009年09月23日 09:24 阅读(59) 评论(2) 分类：program 《一段代码的小小改变对运行时间的巨大影响》

今天写usaco feb 09 gold problems某题

第一次代码如下
   for i:=2 to n do
     begin
      for j:=1 to m do p[j]:=a[j,i]-a[j,i-1];
      fillchar(f,sizeof(f),0);
      for j:=1 to m do
        for k:=a[j,i-1] to ans do
          f[k]:=max(f[k],f[k-a[j,i-1]]+p[j]);
      ans:=f[ans]+ans;
     end;   

max是一个函数
function max(a,b:longint):longint;
  begin
   if a>b then exit(a)
         else exit(b);
  end;   

运行时间见下图
[图片]
有3个点超1s的哦
雷得我要死。。。

然后经wlf大牛指点改成这样

   for i:=2 to n do
     begin
      for j:=1 to m do p[j]:=a[j,i]-a[j,i-1];
      fillchar(f,sizeof(f),0);
      for j:=1 to m do
        for k:=a[j,i-1] to ans do
            if f[k]
               f[k]:=f[k-a[j,i-1]]+p[j];      ans:=f[ans]+ans;
     end;   

完全等价的2种写法，出来的效果却截然不同
[图片]
最后一个点虽然还是超了1s，但是至少只有1个点tle了

然后我又想起来不记得在哪里听到过什么常数优化
代码改成了下面这样

   for i:=2 to n do
     begin
      for j:=m downto 1 do p[j]:=a[j,i]-a[j,i-1];
      fillchar(f,sizeof(f),0);
      for j:=m downto 1 do
        for k:=a[j,i-1] to ans do
            if f[k]
               f[k]:=f[k-a[j,i-1]]+p[j];      ans:=f[ans]+ans;
     end;   

结果呢

[图片]


对比一下有的点快了有的点慢了
但是最后一个点的加速是效果拔群的= =。。

我太费解啦这是什么象限


最后让wlf大牛交到usaco上去

ANALYSIS MODE
Submit solutions for your own enjoyment.
Evaluating 'stock'---------------------
* Compiling PASCAL program stock
  > Compile: OK
* Executing
  > View Test Data:
    Run  #1  Run  #3  Run  #5  Run  #7  Run  #9  Run #11  Run #13
    Run  #2  Run  #4  Run  #6  Run  #8  Run #10  Run #12
  > Run 1: OK [0.002 secs, 2164 KB]
  > Run 2: OK [0.002 secs, 2164 KB]
  > Run 3: OK [0.002 secs, 2164 KB]
  > Run 4: OK [0.002 secs, 2164 KB]
  > Run 5: OK [0.002 secs, 2164 KB]
  > Run 6: OK [0.043 secs, 2164 KB]
  > Run 7: OK [0.145 secs, 2164 KB]
  > Run 8: OK [0.326 secs, 2164 KB]
  > Run 9: OK [0.104 secs, 2164 KB]
  > Run 10: OK [0.123 secs, 2164 KB]
  > Run 11: OK [0.302 secs, 2164 KB]
  > Run 12: OK [0.253 secs, 2164 KB]
  > Run 13: OK [0.549 secs, 2164 KB]
Analysis mode: Program NOT saved for grading.

膜拜评测机
无限膜拜评测机