php实现 合唱队形（算法想清楚在动）

php实现  合唱队形（算法想清楚在动）

一、总结

一句话总结：写一个最长递增子序列的函数，正反两遍扫一下就好。写函数这样不容易错。这个好像可以用二分来优化。

1、算法题怎么提高正确率和节约时间？

算法想清楚了在做，不然会出现莫名其妙，稀奇古怪的错误。

2、php中如何填充数组？

用array_fill();

array array_fill ( int $start_index , int $num , mixed $value )

$a = array_fill(5, 6, 'banana');

Array
(
    [5]  => banana
    [6]  => banana
    [7]  => banana
    [8]  => banana
    [9]  => banana
    [10] => banana
)

二、合唱队形

题目描述

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。 
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 

输入描述:

整数N

输出描述:

最少需要几位同学出列

示例1

输入

复制

8
186 186 150 200 160 130 197 200

输出

复制

4

代码一：

<?php
//谋而后动，之前算法有问题
while($n=trim(fgets(STDIN))){
$numStr=trim(fgets(STDIN));
$arr=explode(' ',$numStr);
for($i=0;$i<$n;$i++){
    $gao[$i]=1;
    $gaoRev[$i]=1;
}
//print_r($arr);
for($i=0;$i<$n;$i++){//遍历每一个人
    for($j=0;$j<$i;$j++){//遍历他们前面的
        if($arr[$i]>$arr[$j]&&$gao[$j]+1>$gao[$i]) $gao[$i]=$gao[$j]+1;
    }
}
for($i=$n-1;$i>0;$i--){//遍历每一个人
    for($j=$n-1;$j>$i;$j--){//遍历他们前面的
        if($arr[$i]>$arr[$j]&&$gaoRev[$j]+1>$gaoRev[$i]) $gaoRev[$i]=$gaoRev[$j]+1;
    }
}
for($i=0;$i<$n;$i++) $ans[$i]=$n+1-$gao[$i]-$gaoRev[$i];
//print_r($gao);
//print_r($gaoRev);
echo min($ans).PHP_EOL;
}

?>

代码二：

<?php
 
function lis($arr){
    $dp = array_fill(0,count($arr),1);
    $ends = array_fill(0,count($arr),0);
    $l = 0; $r = 0; $right = 0;
    $ends[0] = $arr[0];
    for($i = 1; $i<count($arr);$i++) {
        $l = 0;
        $r = $right;
        while ($l <= $r) {
            $mid = floor(($l + $r)/2);
            if($arr[$i]>$ends[$mid]) {
                $l = $mid + 1;
            }else {
                $r = $mid - 1;
            }
        }
        $right = max($right,$l);
        $dp[$i] = $l+1 ;
        $ends[$l] = $arr[$i];
    }
    return $dp;
}
 
//两遍最长递增子序列 和最大
while (fscanf(STDIN,"%d",$N)) {
    $T = explode(" ",trim(fgets(STDIN)));
    $lis1 = lis($T);
    $lis2 = lis(array_reverse($T));
    $lis2 = array_reverse($lis2);
    for($i=0;$i<$N;$i++){
        $lis1[$i] += $lis2[$i];
    }
    $max = max($lis1);
    /* $dp1 = array_fill(0,$N,1);
    $dp2 = array_fill(0,$N,1);
    for($i=0;$i<$N;$i++){
        for($j=$i-1;$j>=0;$j--){
            if($T[$j]<$T[$i]&&$dp1[$j]+1>$dp1[$i])
                $dp1[$i] = $dp1[$j]+1;
        }
    }
    $Tr = array_reverse($T);
    for($i=0;$i<$N;$i++){
        for($j=$i-1;$j>=0;$j--){
            if($Tr[$j]<$Tr[$i]&&$dp2[$j]+1>$dp2[$i])
                $dp2[$i] = $dp2[$j]+1;
        }
    }
    $dp2 = array_reverse($dp2);
     
    $max = -1;
    $sum = 0;
    for($i=0;$i<$N;$i++){
        $sum = $dp1[$i]+$dp2[$i];
        if($sum>$max)
            $max = $sum;
    } */
    echo ($N-$max+1)."
";
 
}
?>