> Плохой тесткейс: http://dl.dropbox.com/u/360558/input_big.txt.gz
(распакуется в 14 мег)
Пример какой-то странный. На нем нельзя убедиться, что программа
работает правильно: все пути дают одинаковый результат, и
пооптимизировать для случая со случайными данными не получится. Откуда
этот файл?
Моя вторая попытка (после прямолинейной первой) - начать считать не
сверху, а снизу, отсеивая пути, которые на очередном шаге добавляют в
результат меньше других.
use v5.10;
#use Data::Dumper;
<>;@v=reverse map{[split/\s/]}<>;
$s=$v[0];
for(1..$#v){
if($q==1){$q++;next}
if($q==2){$q=0;$s=$v[$_];next}
#say Dumper($s);
$c=$v[$_];
$n=$v[$_+1];
if(@$...@$n){
#say join',',@$c;
$m=0;
for(0...@$c-1){
if($$s[$_]){$$s[$_]=$$c[$_]+($$s[$_]>$$s[$_+1]?$$s[$_]:$$s[$_+1]);$m=$$s[$_]if$$s[$_]>$m}
}
p...@$s;
@$s=map{$_!=$m?0:$...@$s
}else{
p...@r,$$c[0]+($$s[0]>$$s[1]?$$s[0]:$$s[1]);
$q=1;
#say '-'x20;
}
}
say for reve...@r;
На простых тестовых данных вроде работает, хотя я не уверен, что здесь
все правильно и будет работать на других данных, например, если
вставить большое число где-то на краю треугольника. Короче, на свалку.
Третий подход через рекурсию. Даже получается уложиться в 256 байт,
причем не убирая "my". Не очень понятно, правда, как отсеиваются
неверные пути, но работает :-)
for(1..<>){
@v=();$h=<>;for(1..$h){p...@v,[split/\s+/,<>]}
print path(0,0),"\n";
}
sub path{
my($x,$y)=...@_;
return 0 if $y==$h;
my$l=path($x,$y+1);
my$r=path($x+1,$y+1);
$v[$y][$x]+($l>$r?$l:$r);
}
Но spoj.pl все равно говорит: "time limit exceeded" :-( Пробовал
избавиться от повторных вычислений:
for(1..<>){
@p=();@v=();$h=<>;for(1..$h){p...@v,[split/\s+/,<>]}
print p(0,0),"\n";
}
sub p{
my($x,$y)=...@_;
return $p[$y][$x]if defined $p[$y][$x];
return 0 if $y==$h;
my$l=p($x,$y+1);
my$r=p($x+1,$y+1);
return $p[$y][$x]=$v[$y][$x]+($l>$r?$l:$r);
}
И здесь "time limit exceeded". Если я правильно понимаю, все равно
приходится пройтись по всем путям? Нет?
--
Andrew Shitov
______________________________________________________________________
[email protected] | http://shitov.ru
--
Moscow.pm mailing list
[email protected] | http://moscow.pm.org
